What does it mean when a computer runs 'faster'? If you have two computers with only one thread, a and b.

And computer a runs twice as fast as computer b.

Does this mean that computer a and can do twice as many operations in a given time in comparison to computer b?

To increase the Hertz of a computer, i.e. the speed of the computer and the number of operations it can achieve with in a given time frame, what has to change in the architecture?

The performance of a computer for most programs cannot be simply derived from the computer's capacity to perform operations (i.e., peak performance). As Shitikanth's answer states, the memory system and other bottlenecks can keep performance below the peak.

In addition, processor frequency is not necessarily proportional to processor performance. It is possible to increase performance without increasing frequency and to reduce performance by increasing frequency.

A substantial number of techniques can be used to increase performance.

Increasing the execution width of the processor (how many operations it can perform in parallel) can also increase performance. While increasing width tends to require reducing the frequency and programs rarely fully utilize the extra width at all times, no modern high performance processor only begins executing one instruction each cycle. (Supporting vector operations is somewhat similar, but that requires more support in software. Likewise using multiple processing cores or multiple threads within a single processing core can provide greater parallel operation while requiring more software effort.)

Speculation can also be used to increase performance. By doing work that might not have been necessarily, it is possible to increase the amount of parallelism available and to reduce execution delay. In current processors this includes branch prediction, out-of-order execution, and hardware prefetching. By predicting the path taken by a branch, the processor does not have to wait until the branch condition and target address are computed before fetching (and even executing) instructions after the branch.

(Increasing the accuracy of branch prediction can be very helpful for some workloads. Reducing the number of branch mispredictions reduces the amount of useless speculative work done by the processor. This can allow more electrical power/thermal budget to be applied to useful work. Such can also allow a deeper pipeline to have an acceptable amount of performance loss from the misprediction penalty. A deeper pipeline allows higher frequency but increases the cost of a branch misprediction--simplistically N pipeline stages of work must be discarded on a misprediction so increasing the number of pipeline stages increases the cost of mispredictions.)

Out-of-order execution allows (usually useful) work to be done while one or more instructions wait for a result from a previous instruction. Increasing the number of "future" instructions that can be considered as candidates for execution increases the processor's ability to tolerate delayed results. Out-of-order execution also allows more operations to execute in parallel by relaxing name dependencies (where an instruction reuses an address/name but does not have a value dependency).

Hardware prefetching speculates that the value prefetched will be used in the near future. Such allows the latency of memory accesses to be reduced. Theoretically prefetching could even be used to distribute the use of memory bandwidth through time (by scheduling useful prefetches during low demand access activity), though prefetching is generally a trade-off between latency and bandwidth use. In addition, it is often more bandwidth efficient to fetch multiple cache blocks that are within a single DRAM page. (Scheduling writebacks to memory can also increase effective bandwidth.)

Cache performance is also an area where computer performance can be improved. Placement policies (where a block is allocated within the physical cache--e.g., Non-Uniform Cache Architectures have been proposed and even implemented) and replacement policies (which block to drop from the cache when a new block is brought into the cache) can increase cache performance by reducing latency in more common or more timing critical cases.

Greater integration of the components of a system can also increase performance by reducing communication delay (and power use which is a significant limiter of computer performance).

In addition, specialized hardware can perform operations faster and/or more efficiently than more general-purpose hardware. (E.g., for decades performance-oriented processors have implemented specialized hardware to perform multiplication rather than reusing the hardware provided for addition. More recently, cryptographic and other specialized hardware has been added.)


Prove propositional formula is a tautology I need to show this formula is a theorem of propositional calculus. I tried assuming antecedent and proving consequent but didn't work for this proof. Do I need to show it is equivalent to true? How should I start? It's not possible to use truth tables.

$(p \rightarrow q) \rightarrow (p \wedge r \rightarrow q \wedge r)$

Background:

In my class, there is no mention to it but I think this form of logic it's called Equational Logic.
Probably, it's based on this book: A Logical Approach to Discrete Math
by David Gries

EDIT:
I was asked to provide more details on the type of proof needed. In my class, I am not allowed to use truth tables to prove this proposition. This is an example:

Here is what the formula states:

  If $p$ implies $q$, then $p$ and $r$ imply $q$ and $r$.

To prove this, you would like to argue as follows. Assume $p$ implies $q$, and suppose that both $p$ and $r$ hold. Since $p$ implies $q$, then $q$ holds. Hence both $q$ and $r$ hold.

How exactly this proof is expressed depends on your proof system.


Counting Deterministic Finite Automata I have a question regarding counting DFAs:

  Given a  Σ = {0, 1} input string, with the state set Q = {1...n}, how would I find the total number of DFAs that can be constructed?

I believe this is a combinatorics problem, but I am not really sure what I would have to multiply.

Thanks.

This is indeed a nontrivial problem. A solution can be found in this paper: Enumeration and Random Generation of Accessible Automata.


what is the best way to approach the construction of nondeterministic PDA's? I'm trying to construct a PDA for $L = \{w0^i1^j \mid w\text{ ends in } 01 \wedge 2i=3j\}$. My understanding is that I have to first accept an arbitrary number of zeros and ones and then nondeterministically guess "$01$" in $w$, however I am stuck with the rest. I understand the condition $i/3=j/2$, but how do I make my PDA accept that? Does it have to be nondeterministic too? How do I approach this?

For the "$w$ part", as you said (or implied) yourself, you don't need the stack at all. After switching to the "$0^i1^j$ part", in some state $s_2$, you can put for the $0$'s in the input alternatingly first an $a$ on the stack, then delete it with a $b$ for the second $0$, then add a $c$ for the third $0$, then start over. By adding only two of the three symbols for each stream of three zeros (as you delete $a$), you get $2/3i$ symbols in the stack which is just equal to $j$. You get a stack like this:
$kbcbc\ldots$ ($k$ being the bottom stack symbol).

Now, you just have to delete each $b$ or $c$ with the ones coming on the input tape and accept iff you reach the bottom of the stack ($k$) when the input is complete.

The second part of the PDA might look something like this ($\lambda$ being the empty word):

$(s_2, 0, k) \rightarrow (s_2, ak)$

$(s_2, 0, a) \rightarrow (s_2, b)$

$(s_2, 0, b) \rightarrow (s_2, cb)$

$(s_2, 0, c) \rightarrow (s_2, ac)$

$(s_2, 1, c) \rightarrow (s_3, \lambda)$

$(s_3, 1, c) \rightarrow (s_3, \lambda)$

$(s_3, 1, b) \rightarrow (s_3, \lambda)$

$(s_3, \lambda, k) \rightarrow (s_e, k)$


Algorithm for computing volume of union or intersection of n-dimensional convex polytopes given their facets? I've googled this problem somewhat pretty extensively, and all the relevant literature understandably deals with 2-d or 3-d cases, rather than the n-d case.

EDIT: Yes, ℝn. I've done many searches combining terms like union, intersection, volume, convex hulls, polytope, etc. I've come across papers like this and this. My math and CS background is weak, but I can tell from the latter paper that this is a difficult problem that I am after.

I appreciate both answers given, unless I misunderstand (probable), I'm not sure that they answer my question? The first answer is just about finding the volume of a polytope given its facets or vertices. I'm aware of algorithms to do so. The second answer may be more on track, but it still raises the question of how to determine IF two polytopes intersect, and where?

Thanks, everyone, for your help so far.

A standard approach is to decompose it into a bunch of triangles (well, the n-dimensional generalization of triangles), then compute the volume of each triangle and sum them up.  Have a look at https://mathoverflow.net/q/979 or https://scicomp.stackexchange.com/q/2881.  Be warned that this could take exponential time.

There are also algorithms for approximating the volume of such a polytope, if that is useful to you.


Expressing iterative version of fold in terms of recursive version 1st Definition. Recursive definition of fold

fold$_{recur}$ (c,h) nil = c

fold$_{recur}$ (c,h) (cons(a, x)) = h(a, fold$_{recur}$ (c,h) x)

2nd definition of fold. Iterative definition

fold$_{itr}$ (c, h) nil = c

fold$_{itr}$ (c, h) (cons (a, x) ) = fold$_{itr}$ (h (c, a), h) x

How do I express fold$_{itr}$ in terms of fold$_{recur}$.

For easier typing let me rename $\mathsf{fold}_{recur}$ to $\mathsf{foldr}$ and $\mathsf{fold_{itr}}$ to $\mathsf{foldl}$ (an additional reason for the renaming will soon be apparent).

Then we have
$$\mathsf{foldr} \,(h,c) \,[x_1, x_2, \ldots, x_n] =
  h(x_1, h(x_2, \ldots, h(x_{n-1}, c) \ldots ))$$
and
$$\mathsf{foldl} \,(h,c) \,[x_1, x_2, \ldots, x_n] =
  h(\ldots h(h(c, x_1), x_2), \ldots, x_n).
$$
That is, your two different folds are also known as the right and left fold in functional programming languages. You are asking how to get the left fold in terms of the right fold. The short answer is "by reversing the list".

Suppose we had a list reversing function $\mathsf{rev}$. Then we could define
$$\mathsf{foldl} \, (h,c) \, \ell =
  \mathsf{foldr} \, ((\lambda (x,y) . h(y,x)),c) \, (\mathsf{rev} \, \ell).
$$
We just need $\mathsf{rev}$ expressed in terms of right fold:
$$\mathsf{rev} \, \ell =
  \mathsf{foldr} \, (\mathsf{append}, \mathsf{nil}) \, \ell
$$
and
$$\mathsf{append}(x, \ell) =
  \mathsf{foldr} \, (\mathsf{cons}, \mathsf{cons}(x,\mathsf{nil})) \, \ell.
$$
You can fold all these definitions into one fat definition of $\mathsf{rev}$, if you want to impress your teacher.


Understanding integer factorization is NP I can see that Integer factorization problem is in NP. I am looking for a simple intuition behind this. For example if we take the problem of sorting the complexity is $n\log n$ for merge/quick sort where $n$ is the number of objects to be sorted. Along that line if take $n$ as the number to be factorized, then factorization algorithm can be run in polynomial time (checking from 2 to $\sqrt{n}$). I understand this is not the case. Please give how to look it this problem compared to that of sorting problem.

The flaw in your reasoning is in considering $n$ as the size of the input.
The input is a number $n$ and its size in memory is $\lfloor \log_2(n) + 1 )\rfloor$ bits.

Thus, $O(\sqrt n)$ is not polynomial in the size of the input.

In order to be polynomial, you would need an algorithm with time complexity $O(\log^k n)$ which would correspond to a polynomial algorithm of order $k$ w.r.t. the size of the input.


Are Context-Free Grammars with only one Production Rule always Unambiguous? Consider the following (Context-Free) Grammars with only one production rule (not including the epsilon production):

$S \rightarrow aSb\;|\;\epsilon$
$\require{cancel} \cancel{S \rightarrow aSSb\;|\;\epsilon}$
$S \rightarrow aSbS\;|\;\epsilon$
$S \rightarrow aSaSb\;|\;\epsilon$
$S \rightarrow aaSaaSbb\;|\;\epsilon$
$S \rightarrow aSbScSdSeSf\;|\;\epsilon$
$\require{cancel} \cancel{S \rightarrow aSSbcSd\;|\;\epsilon}$
etc...

Are all these Grammars unambiguous? Will every Grammar with only one production rule (not including the epsilon production) always be unambiguous? It would seem so, but I'm not totally sure.

  Edit: Vimal Patel has shown that examples like the 2nd and last are, in fact, ambiguous. Discounting these examples and assuming that the non-terminal symbol $S$ never appears next to itself, does my belief still hold?

Grammars that only contain one unique terminal symbol could be ambiguous. (ex. $S\rightarrow aSaSa\;|\;\epsilon$) However, Grammars with at least two distinct terminal symbols seem like they should always be unambiguous.

  Edit II: Vimal Patel has also shown that production rules which both begin and end with the non-terminal $S$ are ambiguous (i.e. $S \rightarrow SaSaSbS\;|\;\epsilon$) discounting this as well, does my belief still hold?

I've tried showing that Grammars like these are $LL(1)$. However, it seems only Grammars of the form  $S \rightarrow aSb\;|\;\epsilon$ are $LL(1)$. Grammars like $S \rightarrow aSaSb\;|\;\epsilon$ are not $LL(1)$. (Illustrated in the parse table below.)

Despite the example Grammar above not being $LL(1)$, it still seems to be unambiguous. Maybe it's simply a matter of using a higher $k$ for $LL(k)$?

In short, are (Context-Free) Grammars with only one production rule (not including the epsilon production) and at least two unique terminal symbols always unambiguous?

I would really love some help, any at all would be greatly appreciated.

Unfortunately, your conjecture is wrong.

For instance $S \rightarrow aSSb | \epsilon$ is ambiguous.

To see that take $w: aabb$. For this string we have following two distinct derivation tree possible. In following derivation trees $e$ represents $\epsilon$

        S                            S
  /  /    | \                  / /    |    \
a  S      S  b                a S     S     b
 / | \ \   \                    |   / / | \
a  S  S b   e                   e  a S  S  b
   |  |                              |  |
   e  e                              e  e

Second counter example:

Consider grammar $S \rightarrow SaSbSaS | \epsilon$
It's easy to see that this grammar is ambiguous. (hint: take $w: abaaba$.)

Third counter example:

Consider grammar $S \rightarrow abSabSab | \epsilon$.
Take $w = abababababab$. It's easy to see that there are two distinct derivation trees.

Actually this grammar is directly derived from grammar $S \rightarrow aSaSa|\epsilon $ by homomorphism $h(a) = h(ab)$.


Can CNN be used for numeric data I have a numpy array of shape N_Samples x 360, as an example, consider the following:

 [ 89 94 56 - - - 55] <-360 length vector
 [ 56 98 55 - - - 98]
 |                  |
 |                  |
 [ 67 55 99 - - - 77] Total N such vectors

There is one label 0 or 1 corresponding to each of the 360- length vector I am asked to train this using CNN but everywhere I am observing that CNN is used for image classification. I am confused about the following:

Is CNN appropriate for such data?
If yes, then how concepts like max pooling and strides are
applicable?
Should we use Conv1D instead of Conv2D?

I will also appreciate if some helpful papers or blogs are provided with respect to this context on how to adjust shapes of input and weight.

Edit:
The 360-length vector is showing ECG signal values of one heartbeat. Keeping R-peak in the middle, I have 180 signal values after and 180 before the R-Peak to have 360 long chunks represent heartbeats (Sampling Rate: 360). I am using it to classify each heartbeat as arrhythmic or non-arrhythmic.

Yes, you can use a CNN.  CNN's are not limited to just images.  Use a 1D convolution, not a 2D convolution; you have 1D data, so a 1D convolution is more appropriate.  A CNN is a reasonable thing to try, but the only way to find out if it actually works or not is to try it on some real data and evaluate its effectiveness.

You can also try simpler methods, like a fully connected network, or even logistic regression.


Is this grammar ambiguous? I have the grammar:

$\qquad \begin{align}
 S &\to S = P \mid S \neq P \mid P  \\
 P &\to NUM
\end{align}$

This grammar suffers from left recursion. To eliminate left recursion, I got:

$\qquad \begin{align}
 S &\to PS' \\
 S' &\to\, = PS' \mid\, \neq PS' \mid \varepsilon \\
 P &\to NUM
\end{align}$

However when constructing the LL(1) parsing table, it turns out the grammar is ambiguous. Is there a way to disambiguate the grammar without changing the generated language, or did I make a mistake somewhere?

This is my work so far:

Non-terminal Nullable First            Follow
S            False    NUM              $
    S'           True     !=, ==, epsilon  $
P            False    NUM              $, ==, !=

Parse Table
     !=       ==    NUM      $
S                   ->PS'
S'  ->!=PS'  ->==PS'        ->epsilon
P                   ->NUM

We can consider $NUM$ and therewith $P$ a terminal symbol. Furthermore, $S$ does only occur once in every derivation. Therefore, if there is any ambiguity, it has to stem from

$\qquad \displaystyle S' \to\, = PS' \mid\, \neq PS' \mid \varepsilon$

Now, that fragment is a right-regular grammar with only one non-terminal whose right-hand sides do not share any prefixes. So clearly every term has only derivation, given by its length and permutation of $=$ and $\neq$.

In total, your grammar is unambiguous. Above observations also suggest that the grammar can be parsed in one pass from left to right with one token lookahead (distinguish $=$ and $\neq$). In fact, the grammar is basically a deterministic (no shared prefixes) and right-regular (replace all $P$ with $NUM$) grammar, so it's certainly an LL(1) grammar.

So I suggest you revisit the construction of the parsing table (your favorite textbook or Wikipedia) -- you must have made a mistake.


Is Directed Graph a Graph? I came across an issue with the definition of a (directed) graph in Sipser's Introduction to the theory of computation, 2nd Ed.

On pp.10, An undirected graph, or simply a graph, is a set of points with lines connecting some of the points. The points are called nodes or vertices, and the lines are called edges, ...

On the same page,

  No more than one edge is allowed between any two nodes.

On pp.12,

  If it has arrows instead of lines, the graph is a directed graph,...

In Figure 0.16 on pp.12, there is an example of a directed graph, an arrow from node 1 to node 2 and an arrow from node 2 to node 1.

So, we have two arrows in opposite direction between two nodes.

I understand all of these basics.

My question is,

  Is directed graph a graph?

As is often the case, using a formal definition is helpful:

Let $V$ a finite set. $G=(V,E)$ is

a graph if $E \subseteq \left\{\{v_1, v_2\} \mid v_1, v_2 \in V \right\}$ and
a digraph if $E \subseteq \left\{(v_1,v_2) \mid v_1, v_2 \in V\right\}$.

Note the central difference: edges are sets in graphs and pairs in digraphs. In particular, simpleness is implied by this definition. Extending the definition is also easy:if $E$ was a multiset, you could have non-simple graphs. If the edges had more than two components, you'd have hypergraphs.

Disclaimer: People define (di)graphs in different ways; this is one very common variant. For example, if you are uncomfortable with digraphs (formally) not being graphs, you define them like this:

Let $V$ a finite set and $E \subseteq V^2$. We call the pair $G=(V,E)$ a graph. We say

$G$ is undirected if and only if $(v_1,v_2) \in E \Longleftrightarrow (v_2,v_1) \in E$ and
$G$ is directed otherwise.

This defines undirected graphs as special cases of directed graphs. Note that with this definition, extensions to labeled graphs (edges get markings) may be awkward: We want the complete digraph with to be different from the complete undirected graph (as the former has two labeled edges between between every pair of nodes, the latter only one); by this definition, they are the same. Note how the first definition I gave circumvents this issue nicely; sometimes definitions are (re)made with later needs in mind.


Communication between hardware components We know that each component has different frequencies, but what happens when a fast component directly comunicates with a slow one?

I think what you're asking is how two machines or components, which run at different clock speeds/phases, can communicate. The short answer is that the receiver synchronises to the sender.
In low-speed communication channels (e.g. I²C), this can be achieved with an explicit clock line. Essentially, the sender has a separate wire that is the transmission clock. This is also generally the way that things work with parallel busses (e.g. where you send 8 bits over 8 wires plus a clock).
This doesn't work as well at high speed, because a small difference in the lengths of two wires can cause signals to arrive at different times. It also doesn't work over channels where there you don't or can't have more than one "wire", such as radio.
If you only have one "signal" (be it a single pair of wires, single radio frequency, or what have you), you are in the domain of line coding.
In that case, the receiver can synchronise by looking for edges in the source signal. There is an agreed-upon clock rate, which neither end can reproduce perfectly. But if the sender sends the message 00101001, for example, every time the bit flips from 0 to 1 or 1 to 0, that is something that the receiver can synchronise to.
Exactly how to synchronise clocks is a question for electronics engineers, who can explain techniques like phase-locked loops to you better than I can. It's a little subtle because the receiver can detect edges, but ideally wants to take its sample from the half-way point between the leading edge and the trailing edge, so there has to be some kind of delay involved.
But what if there are no edges? If the transmitter wants to send a whole bunch of zeroes, how does the receiver synchronise then?
The way around this is to design a code which does have transitions. RS-232, for example, specifies that each byte begins with a start bit, and ends with one or more stop bits, and there is a zero between the two frames, so every byte effectively has the bits "101" between bytes.
Medium-speed channels where retransmission is not an option (e.g. digital broadcast, satellite/spacecraft communication, or recording media such as optical disks) will often use error-correcting codes to achieve the same effect. Not only do you get error correction, the extra redundancy gives plenty of opportunity for clock synchronisation.
And then, you get into physical problems to do with the fact that you're communicating over physical wires or physical radio signals.
Over wires, for example, it's desirable to design a code with approximately the same number of 0 bits and 1 bits, a property known as DC balance. Real pairs of wires will act like a capacitor at high speed, and so if you have (say) more 1's than 0's, they will retain a charge and hence resist sending 1's. An example of a code designed for this is 8b/10b, which is used in a lot of modern high-speed serial communications such as HDMI, SATA, Gigabit Ethernet, and USB 3.0.
See this question from electronics.SE for further details.
Radio communication (e.g. Wi-Fi and cellular telephony) has its own problems that I can't really cover here, even if I understood it all. You have to protect against the Doppler effect, destructive interference caused by reflections, and so on.


What exactly is bigO notation? I've heard of bigO notation but I don't really understand how do I determine it for my code and what exactly does it represent?
I heard that there are two:

RunTime
Memory Complexity

How can I learn to use it?

Big O notation is nothing other than dividing functions into classes based on their asymptomatic growth behavior. What those functions are a measure of is entirely independent of Big O.

Big O is most commonly used to classify the function that maps an input size to the longest time an algorithm runs on any input of that size. But it could be used instead for average running time or shortest running time, or to measure space usage, cache misses, messages sent over the network, etc.

We use big O because we don't generally care about the exact value of these functions, just about how fast they grow. It's an abstraction that lets us see the general pattern but omits constant and lower order factors.


Is there a $O(n\frac{\log{n}}{\log{k}})$ sorting algorithm? I am trying to figure out a sorting algorithm which can be used in $O(n\frac{\log{n}}{\log{k}})$ sorting time. I am allowed to use $k$ registers that can store key value pairs and these registers can insert a key value pair and return a key value pair in constant time. And when popping from one of these registers, it will return the smallest key.

So what I have so far is, I am thinking about having a hash function with value (highest value in array size $n$) and then put that into the registers, then will pop the registers (Which will return the smallest key value) and add those sorted values back into the array. But the main problem I have is I do not know how large $k$ will be so when I pop the values from the registers, I may have to put more values back in the registers, and was wonder how to go about this.

So the answer I ended up going with is making the value the key itself, then adding the key and the value to the registers. Once the registers are full, we will pop the smallest key, and do a binary search on where we should be inserting the value into a new sorted array which we will be returning.


What is the difference between exhaustive search & combinatorial search? I get used to think exhaustive search and combinatorial search are same, but I got confused by reading a paper!

What is the difference between  exhaustive search & combinatorial search ?

My two cents: exhaustive search is also known as brute force search, an approach in which you have no better strategy than to explore the entire search space, testing every possible candidate solution. Two examples were given by @Yuval Filmus. If you are really unlucky, the solution may well be the last candidate explored, or one of the last ones. Therefore, in general exhaustive search is in the worst case linear in the size of the search space to be explored.

On the other hand, combinatorial search instead is a smarter kind of search, which usually exploits one or more pruning strategies to avoid testing all of the possible candidate solutions. In this case, you can safely discard some candidates (depending on the particular algorithm of course) and therefore you can save precious time. An example of combinatorial search is, for instance, branch and bound. Here, you may safely skip some subtrees since, depending on your particular optimization problem, you know in advance that no node within a certain subtree can yeld a better solution than the current one during the execution of your algorithm.


Algorithm to compute decomposition of a union of sets to a disjoint union of intersections A union of sets can be decomposed into a disjoint union of intersections. Rather than writing confusing notation, this is easiest to to see in an example of three sets.

This clearly generalizes. If we want to calculate the disjoint pieces, we have to compute $2^n$ intersections, where $n$ is the number of sets.

However, if our sets were nested, i.e. $A_1 \subseteq A_2 \subseteq ... A_n$, we need only to compute $n$ intersections of the form $A_i \cap A_{i+1}^c$. The point is if we did our original exhaustive "binary search" computing $2^n$ intersections we would find that most of these intersections are empty, so we are wasting computations.

My question is, what if we had $n$ sets where the vast majority are nested, but a few aren't and we don't know which. Can we compute an $O(n)$ number of intersections to find the disjoint pieces?

No, not $O(n)$.  Suppose $0.9n$ are nested and $0.1n$ are not nested (and are unrelated).  Then there can be at least $2^{0.1n}$ different pieces, which is not $O(n)$.

You can find the nesting structure in $O(n^2)$ time by testing all pairs of sets to see which are subsets of the other.


Proof of inequality $\lceil x \rceil \le x+1$ I went through the Master Theorum extension for floors and ceiling section 4.6.2 in the book Introduction to Algorithms
It had the following statement:

Using the inequality $\lceil x \rceil \le x+1$

But I haven't seen the inequality anywhere and could not understand the verifiability of inequality.
Instead the Chapter Floors and ceilings defined floors and ceilings as:
$$x-1 \lt \lfloor x \rfloor \le x \le \lceil x \rceil \lt x+1 $$
Please clear my doubt over this.
On how to use this identity and which identity to be considered when because both of them define completely different inequalities.
Thank you.

The definition of $\lceil x \rceil$ is:

$\lceil x \rceil$ is the minimal integer $n$ such that $n \geq x$.

(The existence of such an integer makes the reals an Archimedean field.)
Let us assume, for the sake of contradiction, that $\lceil x \rceil \geq x + 1$. Then $\lceil x \rceil - 1 \geq x$. Since $\lceil x \rceil - 1$ is also an integer, this contradicts the definition of $\lceil x \rceil$. Thus $\lceil x \rceil < x + 1$.
It is also easy to check that the inequality is tight, in the sense that $1$ cannot be replaced by any smaller $\theta$. Indeed, if $\theta = 1 - \epsilon$ for $\epsilon \in (0,1)$, then $\lceil \epsilon \rceil = 1 = \epsilon + \theta$.


Why would a function be tabulated in advance and then retrieved? Given some function and assuming no concern for the time to compute the co-domain for its domain, when might it be preferable to compute and tabulate in advance the co-domain results of the function, and then retrieve it from the table rather than compute it?

For example, if the domain for $f(x)=x^2$ were sufficiently small, why, if ever, would one wish to compute the co-domain and then, for a given x, retrieve the stored value of $f(x)$?

This sort of computation can be used for optimization purposes.

A classic simple example is computing the Fibonacci sequence. Apart from the base cases, $f(n) = f(n - 1) + f(n - 2)$, but then $f(n+1) = f(n) + f(n-1)$ and $f(n+2) = f(n+1) + f(n)$, and so on. So the value of $f(n)$ for each $n$ is used repeatedly. The effect is more dramatic if you use the naïve recursive algorithm.

This computation can be significantly optimized if we keep the values of $f$ that we have already computed and simply access the result as we need it.

If all we want to do is compute $f(n)$ for some $n$ once, this is already an observable improvement in the asymptotic running time of the algorithm (and it shows up very quickly in practice too). If we need to repeatedly use values of $f$ in a larger program, the improvement is even more effective.

Doing things like this form part of a technique called memoization, which is closely related with dynamic programming.


$2^1 + 2^2 + \cdots + 2^8$ in binary Maybe these are silly question. I know almost nothing about computer science, so please let me know in the comment section if I should edit anything or delete it.

Let's say I have a function that randomly selects 8 choices of 0 or 1. Would it be written as one byte together? For example, if all choices came out as 1, would it be written as 11111111?
Also, let's say another function can select the amount of choices. Any between 1 and 8 choices of either 0 or 1. As an example, if 3 choices were selected and all came out as 1, will it be written as 111? If so, how will the program know when to go to the next function in the case that every function had to select between 1 and 8 choices of 0 or 1?

In the binary system (much like in all numbering systems), order has meaning. If you write $0110$ this means $0\times2^3+1\times2^2+1\times2^1+0\times2^0$. Similarly, $11111111$ means $1\times2^7+1\times2^6+1\times2^5+1\times2^4+1\times2^3+1\times2^2+1\times2^1+1\times2^0=255$.

Now, assuming you had a function that produced a random bit as output, you would have 8 distinct bits if you called that function 8 times, which would form no kind of greater structure (that is, you would have e.g., 8 ones, but they would not mean 255 because they are not in an ordered structure, it's just 8 disjoint pieces of data).

On the other hand, if your function randomly selects the values of 8 bits and returns them, you would just have an array (or vector) of bits, which also do not represent a number.

In that sense, you can have the function output any number of bits you want. If you want two bits, you get 11 or 01 or 00 or 10, if you want three bits you get 111 or 000 or 100 or 010 or 001 or 110 or 101 or 011 etc. Note that in the way that you have phrased the question, these would not actually translate into numbers.


Run time of recurrence with five uneven calls I am trying to figure how to find an upper bound for the running time of a given recurrence relation (without proving the bound) using the Iteration method. The recurrence is:

$$T(n)=2T\left(\frac{n}{5}\right)+3T\left(\frac{n}{10}\right)+n$$

I tried to iterate over it and got:

$$\begin{align}
T(n)& =2T\left(\frac{n}{5}\right)+3T\left(\frac{n}{10}\right)+n\\[0.5em]
& =2\left(2T\left(\frac{n}{25}\right)+3T\left(\frac{n}{50}\right)+\frac{n}{5}\right)+3\left(2T\left(\frac{n}{50}\right)+3T\left(\frac{n}{100}\right) + \frac{n}{10}\right)+n\\[0.5em]
& =10T\left(\frac{n}{25}\right) + 6T\left(\frac{n}{50}\right) +9T\left(\frac{n}{100}\right)+\frac{7n}{10}
\end{align}$$

And couldn't know how to continue from here, any hints?

I'll offer up a more general claim and a proof, you can apply it to your scenario as needed.

The Uneven Split Theorem

Let $c$ and $k$ be positive constants.

Then let $\{a_1, a_2, \dots a_k\}$ be positive constants such that $\sum_1^k a_i < 1$.

We also must have a recurrence of the form:

$$\begin{align}
T(n) & \leq c & 0 < n < max\{a_1^{-1}, a_2^{-1}, \dots a_k^{-1}\}\\
T(n) & \leq cn + T(a_1 n) + T(a_2 n) + \dots T(a_k n) & n \geq max\{a_1^{-1}, a_2^{-1}, \dots a_k^{-1}\}
\end{align}$$

Claim

Then I claim $T(n) \leq bn$ where:

$$b = \frac{c}{1 - \left(\sum_1^k a_i\right)}$$

Proof by Induction

Basis: $n < max\{a_1^{-1}, a_2^{-1}, \dots a_k^{-1}\} \implies T(n) \leq c < b < bn$

Induction: Assume true for any $n' < n$, we then have

$$\begin{align}
T(n) & \leq cn + T(\lfloor a_1 n \rfloor) + T(\lfloor a_2 n \rfloor) + \dots + T(\lfloor a_k n \rfloor)\\
& \leq cn + b \lfloor a_1 n \rfloor + b \lfloor a_2 n \rfloor + \dots + b \lfloor a_k n \rfloor\\
& \leq cn + b a_1 n + b a_2 n + \dots + b a_k n\\
& = cn + bn \sum_1^k a_i\\[0.5em]
& = \frac{cn - cn \sum_1^k a_i }{1 - \left(\sum_1^k a_i\right)} + \frac{cn \sum_1^k a_i}{1 - \left(\sum_1^k a_i\right)}\\[0.5em]
& = \frac{cn}{1 - \left(\sum_1^k a_i\right)}\\
& = bn & \square
\end{align}$$

Then we have $T(n) < bn \implies T(n) = O(n)$.

We also know $T(n) = \Omega(n)$ by the recurrence definition, therefore $T(n) = \Theta(n)$.

Next apply it to your recurrence of the form:

$$T(n)=cn + T\left(\frac{n}{5}\right) + T\left(\frac{n}{5}\right) +T\left(\frac{n}{10}\right) + T\left(\frac{n}{10}\right) + T\left(\frac{n}{10}\right)$$

I'll leave this for you to figure out the $a_k$'s and $b$.

A pretty quick rule of thumb if the work done per recursion is linear $(cn)$:

If the constants in the recursion calls sum to less than $1$, it's $O(n)$.
If the constants sum to exactly $1$, it's $O(n \log n)$.


Performance of row- vs. column-wise matrix traversal Scott Meyers describes here that traversing a symmetric matrix row-wise performes significantly better over traversing it column-wise - which is also significantly counter-intuitive.

The reasoning is connected with how the CPU-caches are utilized. But I do not really understand the explanation and I would like to get it because I think it is relevant to me.

Is it possible to put it in more simple terms for somebody not holding a PhD in computer architecture and lacking experience in hardware-level programming?

In today's standard architectures, the cache uses what is called "spatial-locality". This is the intuitive idea that if you call some cell in the memory, it is likely that you will want to read cells that are "close by". Indeed, this is what happens when you read 1D arrays.

Now, consider how a matrix is represented in the memory: a 2D matrix is simply encoded as a 1D array, row by row. For example, the matrix $\left(\begin{array}{ll} 2, 3 \\4, 5\end{array}\right)$ is represented as $2,3,4,5$.

When you start reading the matrix in cell $(0,0)$, the CPU automatically caches the cells that are close by, which start by the first row (and if there is enough cache, may also go to the next row, etc).

If your algorithm works row-by-row, then the next call will be to an element still in this row, which is cached, so you will get a fast response. If, however, you call an element in a different row (albeit in the same column), you are more likely to get a cache miss, and you will need to fetch the correct cell from a higher memory.


Thirty-one game. Prediction of the winner I have a problem with creating an algorithm to predict a winner of thirty-one game.

Players from a deck of cards, take the Ace, 2, 3, 4, 5, and 6 of each suit. These 24 cards are laid out face up on a table. The players alternate turning over cards and the sum of the turned over cards is computed as play progresses. Each Ace counts as one.
The only limit is the sum value of stacked cards: it cannot exceed 31. The player who cannot make a move loses.

My task is to determine the winner in the game based on stack of cards put aside. We assume that both players play perfectly.

For example:

356656 means gameplay: player A puts down 3, player B puts down 5, player A puts down 6, player B puts down 6, player A puts down 5, finally player B puts down 6 and wins because player A cannot make any move.

356656 -> winner B
35665 -> winner B
3566 -> winner A
111126666 -> winner A
552525 -> winner A
2 -> winner A

This kind of question can be answered using a simple recursive procedure.

A state of the game consists of:

a sequence $a_1,\ldots,a_n$ describing how many cards of each value in $1,\ldots,n$ remain (in your case, $n = 6$).
the number of "points" remaining $p$.

Your initial state is $\vec{a}=(4,4,4,4,4,4)$ and $p = 31$.

For each state $(\vec{a},p)$, there is a sequence of possible moves, which in this case is
$$
N(\vec{a},p) = \{ (a_1,\ldots,a_{i-1},a_i-1,a_{i+1},\ldots,a_n),p-i : i \in [n], a_i \geq 1, i \leq p \}.
$$
Let us say that a position is winning if the first player wins when starting from it. A position is winning iff there is a next position which is losing, and so the winning predicate $W(\vec{a},p)$ satisfies the recurrence
$$
W(\vec{a},p) = \bigvee_{\vec{b},q \in N(\vec{a},p)} \lnot W(\vec{b},q).
$$
When $N(\vec{a},p) = \emptyset$, the disjunction is empty, and so $W(\vec{a},p)$ is false.

In your case, you can easily calculate $W((4,4,4,4,4,4),31)$ to be true. The winning moves are $1,2,5$.

Here is sage code that calculates this:

@CachedFunction
def game(cards, target):
    return [i for i in range(len(cards)) if target >= i and cards[i] >= 1\
    and len(game(cards[:i] + (cards[i]-1,) + cards[i+1:], target-i)) == 0]

This code also allows cards with value zero. You can run it like so:

sage: game((0,4,4,4,4,4,4),31)
[1, 2, 5]

It outputs the set of winning moves (if any).


Genetic Algorithm - Fit max circles inside box I am using a genetic algorithm to find the best way to pack circles inside a box without each touching the others and filling as much space as possible. My doubt is if an individual from a generation must be a circle or all the circles.

Can anyone help me on how would I go from here? Thank you

In genetic algorithms, each individual should be a candidate solution to the problem.  You're trying to find a packing of circles into the box, so each individual should be a complete packing that specifies the location of all the circles.


ACC0 and the majority gate I am missing something obvious here. Does ACC0 reach a ceiling AC0[m] with m being constant?
By another description, ACC0 can use any m, which can trivially test modulus gates from [n/2,n] over all inputs. Any modulus active in that range indicates MAJ returns true, implementable as an OR over the current range of gates.

It does not reach a constant ceiling, but the modulo gate cannot depend on the input's length, e.g. $\bmod n/2$ gates are not allowed. You must decide on the constants while constructing the circuit, independently of the input/input size. See the definition in Arora and Barak's book, where they first define $ACC0(m_1,...,m_k)$ which corresponds to circuits with $\bmod m_1,...,\bmod m_k$ gates, and then define $ACC0$ as the union of $ACC0(m_1,...,m_k)$ over all integer $k$-tuples.


How many knights can be placed on an n-by-m chessboard? I have a task, and its essence is as follows: how many knights on an $n \times m$ board can be set so that they do not attack each other. I am wondering if there is any mathematical solution to this problem, except for the algorithmic one.

For an 8*8 chess board,

You need to observe that when 2 knights beat one another they lie on cells of different colors.
We can generate a solution by placing 32 knights in the 32 white cells so that no 2 knights beat each other.
To prove that this is the optimal solution, we can group our rows into pairs (1,3),(2,4),(5,7),(6,8). Let us consider the row pair (1,3). Consider the pairs of cells (R1C1,R3C2) and (R1C2,R3C1). We can see that we can place only 1 knight in the cell pair (R1C1,R3C2) and only 1 knight in the cell pair (R1C2,R3C1). Continuing this idea, we can show that we cannot place more than 32 knights in an 8X8 chessboard.
We already have an arrangement of 32 knights from point 2. Hence, the solution described in point 2 is optimal.

Expanding the above idea, below are the maximum no. of knights that can places such that no 2 beat each other on any N*M chessboard.

If both N and M are odd, then the solution is ((N*M)+1)/2
If either N or M is even, then the solution is (N*M)/2


How the kernel works in a LCF theorem prover I heard that there is some mechanism in LCF-based theorem provers that only allows some functions to create values of type theorem. I believe these are based on abstract data types.

Could someone sketch in pseudo-code how does this work? (in case the above is correct)

If I recall correctly, this was chapter 5 or 6 of John Harrison's Handbook of Practical Logic and Automated Reasoning.

Jon Sterling wrote some notes for a recitation a year or two back, specifically for an LCF prover using sequent calculus.


Proof of Co-Problem being in NP if Problem is in NP using negated output Given any problem $P$ that we know of being in $NP-\text{complete}$, where is the flaw in the following proof?
Given a problem $Co-P$ which is the co-problem of $P \in NP-\text{complete}$, $Co-P$ is at least in $NP$ because the following algorithm can always be given:
Co-P(J):
    bool res = P(J)
    return !res

Where $Co-P(J)$ is the algorithm solving $Co-P$ and $P(J)$ is the nondeterministic polynomial algorithm solving P.
Why is this not correct?

A problem is in NP if for all instances where the answer is “Yes” you can guess a hint and verify it in polynomial time. Nothing at all is said for instances where the answer is “No”. That distinction between “Yes” and “No” answers is essential.
What your proof attempt shows is that if a problem X is in NP, then the co-problem “Does X have the answer ‘No’” is in co-NP, as we would expect, and says nothing about NP.


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

There are two things I would like to show:

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

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

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

Hint: $S_l - S_r$ is the sum of $2n$ independent variables $X_1,\ldots,X_{2n}$, with $\Pr[X_i = 1] = \Pr[X_i = -1] = 1/2$.


Finding a regular expression of a language Our alphabet is {a,b} and we need to find a regular expression for the language of all words of the form $a^*b^*$, whose length is a multiple of 3.

Obviously $(aaa)^*(bbb)^*$ is one of the options, but I just can't formalize more options.

Any help will be appreciated.

You have to put your triplets, and use Kleene star: $$(aaa)^*(bbb)^*$$

Now, add cases where number of $a$ is not divisible by 3, say aabbbb, as alternative.
$$ (aaa)^*(bbb)^* + (aaa)^*aab(bbb)^* + (aaa)^*abb(bbb)^*$$


AVL tree size in terms of height For AVL trees, which one of the following is possible as the tree size (expressed in term of the tree height h)? Recall that the size of a tree is the number of nodes in the tree.

A. $Θ(h^{2.1})$
B. $Θ(1.1^h)$
C. $Θ(1.9^h)$
D. $Θ(2.1^h)$

So this question came up on my midterm and I don't understand why the answer is C and not D.
How I solved it is:
$h=log(n)$
so $n=2^h$.
Does it have anything to do with the fact that it's asking for a tight bound?

Let $n$ be the size of an AVL tree with height $h$. Then we have
$$ \log_2(n+1) \leq h \leq c\log_2(n+2) + b$$
where $c\approx 1.44$ and $b\approx -0.328$. So,
$$ 0.8(1.6)^h\lt df^h=2^{-b/c}\left(2^{1/c}\right)^h=2^{(h-b)/c}-2 \leq n \leq 2^h -1 \lt 2^h $$
where $d\approx 0.85$ and $f\approx 1.618$.

Now you can see that the only number among 1.1, 1.9 and 2.1 that is between 1.6 and 2 is 1.9. Hence the answer is C.

I would not say it is asking for a tight bound.


When is epsilon a part of the result of computing the right quotient? The right quotient of two languages is defined as

$$L_1/L_2=\{ x \mid  xy \in L_1 \text{ and } y \in L_2 \}.$$

Example:
$L_1=\{ab,aab,baa\}$ and
$L_2=\{b\}.$

I read somewhere that $L_1/L_2=\{a,aa,\varepsilon\}$ but I cannot understand why $\varepsilon$ is contained in the quotient.

In words, your definition says "The right quotient, written $L_1 / L_2$, is defined to be the set of all strings $x$ such that $xy$ is a string in $L_1$ for some string $y$ in $L_2$." According to this definition, the empty string is a member of the right quotient if and only if there is a common string in the two languages. In symbols, $\epsilon \in L_1 / L_2 \iff L_1 \cap L_2 \neq \emptyset$. In particular, this is not the case in your example, hence, the empty string is not in your right quotient.


Transforming a byte with a subset of a small, fixed set of values and xor into any other value If I have some collection of bits, -- a byte, say -- of arbitrary value then I can transform it into some other value by means of exclusive-oring it with a subset of (in this case) eight fixed values, each affecting a single bit 0x80, 0x40, ... 0x01: every possible value is represented by some combination of operations from any given starting point.

But, clearly there are other sets of eight values which achieve this. For example 0b1xxxxxxx, 0b01xxxxxx, 0b001xxxxx, 0b0001xxxx, 0b00001xxx, 0b000001xx, 0b0000001x, 0b00000001 clearly satisfy these criteria and are a relatively large set of such values (as the x's can be distinct). (Proof: use the first value to get the msb correct then the second to get the second-msb correct, etc).

However, some sets clearly do not have this property, for three bits 0b101, 0b110 and 0b011, for example, clearly do not as every operation preserves parity.

I am interested in various aspects of the above property from a practical standpoint for a numerical computational model. I am not a theoretical computer scientist, but have studied these things in the last century, so I am vaguely aware that what I need to look at may amount to groups, Galois Fields, LFSRs, etc.

Could someone point me in the right direction so that my learning can be more directed than random flailing around textbooks and wikipedia? Just some signposts as to the names of the relevant fields of study, the great theorems/problems/categories and their names, the useful techniques, etc, would be fine.

You have recalled the correct category, "linear-algebra".

Let us see how we can interpret xor in the terms of linear-algebra. Here is the computation rules for xor.
$$0\oplus0=0$$
$$0\oplus1=1$$
$$1\oplus0=1$$
$$1\oplus1=0$$
If we consider 0 and 1 as the zero element and the unit element of the binary field $\Bbb F_2$, the simplest finite field, then we can see $\oplus$ is none other than the addition in $\Bbb F_2$.
$$0+0=0$$
$$0+1=1$$
$$1+0=1$$
$$1+1=0$$

That means, if we xor a string of 3 bits to another string of 3 bits, we are actually adding two vectors $\vec a$ and $\vec b$ in the three-dimensional linear space $\Bbb F_2^3,$
$$\vec a+\vec b=\vec c$$
For example, $(0,1,0) + (1,1,0)=(1,0,0)$.

If we fix the second vector, the addition by the second vector is a linear transformation from $\Bbb F_2^3$ to $\Bbb F_2^3$. All these transformations form a 3-dimensional linear space over $\Bbb F_2$ with basis
$$\{\text{addition by (1,0,0)}, \text{ addition by } (0,1,0), \text{ addition by (0,0,1)}\}.$$
Given a set of vector in $\Bbb F_2^3$, all combinations of the additions by those vectors can transform any vector to another vector if and only those vectors are linearly independent.

For example, "three bits 0b101, 0b110 and 0b011" "do not have this property" because, $(1,0,1)+(1,1,0)+(0,1,1)=(0,0,0)$ in $\Bbb F_2^3$, i.e, those three vectors are not linearly independent.

Here is a counting exercise.

(Exercise) Show the number of sets of such strings of 3 bits is $(2^3-1)*(2^3-2)*(2^3-2^2) = 168.$ In general the number of set of such string of n bits is $(2^n-1)(2^n-2)\cdots(2^n-2^{n-1}).$


Finding the maximum of a bitonic sequence Given to us is an array $B[1],\ldots,B[n]$ as input, which satisfies the following property: there exists a special index $i^* ∈ \{1, \dots , n\}$ such that $$B[1] < B[2] < \dots < B[i^*− 1] < B[i^*] > B[i^* + 1] > B[i^* + 2] > \dots > B[n].$$

It is noted that the index $i^*$ is not given as part of the input.

The question asks me to design an algorithm for computing the index $i^*$, whilst trying to ensure it has the smallest running time possible.

I just wondered if anyone could produce this algorithm and explain your thought process on how you came up with it if possible? Stuck on these type of questions

The first thing that comes to my mind after reading your question is as follow. Draw the sequence as a graph given below. Each $B[i]$ you can think of a point in the graph given below.

The idea to do binary search should be clear from the question as input sequence is almost sorted. Now if you guess the peak point then you are in a good position, but during the binary search if you choose a number which will give you two cases.

The above two cases are the cases in which you need to think, but if you have tried few problems on binary search then now the problem will be easy to solve. More formally you can see the yuval's answer. You ask for the thought process, I have tried to give you my thought process. For any two persons thought process is different, there may be many other way to visualise the problem you have described.


Why does the Toffoli gate output c XOR (a AND b) instead of just a AND b? The Toffoli gate takes in three inputs and gives out three outputs, and is often referred to as the quantum AND gate.

It takes in a,b,c and gives out a, b, c XOR (a AND b).

Why does it do that, instead of just giving out a,b,b AND c?  or a,b,(a AND b)?

As the comments said, if it worked like i asked, it would neither be reversible, nor a unitary matrix.

Both things are required for quantum computing!


Simple lower bounds against AC0 It is known that $Parity \notin AC^0$ (nonuniform), but the proof is rather involved and combinatorial. Are there simpler, but weaker lower bounds, say for $NP \not \subseteq AC^0$ or $NEXP \not \subseteq AC^0$?

For example, can nontrivial simplifications be obtained in the proof of $NEXP \not \subseteq ACC^0$ to deal only with the special case of $AC^0$?

I guess it depends on your point of view, but the proof via approximating polynomials (along the lines of Razborov-Smolensky) that Parity isn't in AC0 is not so involved...

The natural way in which one would modify the proof that "NEXP is not in ACC0" to yield "NEXP not in AC0" would be to give a SAT algorithm for AC0 circuits that beats exhaustive search. However, all known SAT algorithms of this kind actually use the same or similar techniques as the "Parity not in AC0" lower bounds, so the proof would not get any simpler. (It would be interesting to find an AC0 SAT algorithm where this is not the case.)


Find shortest path that goes through at least 5 red edges Let $G=(V,E)$ be a directed graph, $\omega : E \rightarrow R$ a weight function, and $s,t \in V$ a pair of different nodes. It's given that $G$ doesn't have a negative cycle. Moreover, 10 of its edges are colored in red (let's say that the rest are colored in blue).

I want to find an efficient algorithm that find the shortest path between $s$ and $t$ that goes through at least 5 different red edges.

Notice that going more than once through the same red edge is still considered as going through 1 red edge in the path.

One idea that I had was creating a graph $G'$ that will have a copy of every node for every possible set of red edges in $G$. That means that if we go through some red edge $e$, then the path will "move" to a variation of $G$ where $e$ is colored in blue and all the rest is the same.

However in this solution I will have to copy each node and each edge around 400 times. This will result in the same complexity asymptotically, but with such a big constant it seems really not efficient.

Another idea, was to somehow build the new graphs "on the run" of Bellman-Ford algorithm, but I don't really know how to do it.

I'll appreciate some help.

What about reducing the problem first ?

UPDATED with more details :

Build 2 node subsets:

Vs contains s and the 10 reached nodes of the red edges (called a1, a2, ..., a10 hereafter). This is a 11 nodes set.
Vt contains t and the 10 sources nodes of the red edges (called b1, b2, ..., b10 hereafter). This is another 11 nodes set.

Build a distance matrix M from Vs to Vt (11x11)
Do 11 Dijksta explorations, one starting from any node of Vs to reach all nodes of Vt. So you get 11 shortest distances to report in the matrix M.
The diagonal terms are irrelevant (s->t or ak->bk).
For each row of M, add wi (the weight of the red edge) to all elements (0 for s row). This is the price of crossing the red edge.
Build an new graph G' with 11 nodes. node N0 for s&t and nodes Nk for each red edge (ak & bk). Then create all edges using matrix entry:
w(Ni -> Nj) = M[i][j].
Now your initial problem is equivalent to find a loop of 6 nodes containing N0 in G'.
Use any method to test all combinatoric for instance Apass.Jack one. This step in NP complete.


Solving recurrences using substitution method I already have a solution for this problem but it's just not making sense to me.

Here is the problem (It's from Introduction to Algorithms by CLRS found in CH.4):

  Show $T(n) = 2T(\lfloor n/2 \rfloor +17)+n$  is $O(n \log n)$

This is what I have so far:

So Assume $T(k) \leq cn\lg n$, for $k<n$.

$\qquad \begin{align*}
  T(n) &= 2T(\lfloor n/2 \rfloor +17)+n \\
       &\leq 2c(\lfloor n/2 \rfloor +17)\lg(\lfloor n/2 \rfloor + 17) +n \\
       &\leq 2c(n/2 + 17) \lg (n/2 + 17) + n \\
       &= c(n + 34) \lg((n+34)/2)+ n
\end{align*}$

And this is where I stop understanding what is going on. Looking at the solution to this problem tells me:

  Note that $(n + 34)/2 \leq (3n)/4$ for $n \geq 68$
  so that $\lg((n + 34)/2) \leq \lg((3n)/4) = \lg(n) + \lg(3/4)$ for $n \geq 68$.

But it fails to tell me why/how we know that $(n+34)/2 \leq 3n/4$ for $n \geq 68$. Where did this number come from and how would I arrive at this if I did not know the solution beforehand?

The complexity in your proof is that you have addition in you logarithm, and you need that complexity to go away. So lets get rid of that 34, by just making $n \ge 34$, so now

$$\log\left( \frac{n + 34}{2} \right) \le \log\left( \frac{n + n}{2} \right) = \log(n).$$

I am not sure why the book chose 68, but really its the same argument. If $n \ge 68$, then $n/2 \ge 34$. Thus

$$\log\left( \frac{n + 34}{2} \right) \le \log\left( \frac{n + n/2}{2} \right) = \log\left( \frac{2n + n}{4} \right) = \log\left(\frac{3n}{4}\right) = \log(n) + \log(3/4).$$


Fill the time slot with the best match If I have the following array: pieces = {35,15,20,25,30,10}  and the time slot is 80 minutes.
How do I do the following:
1. Fill the time slot with any pieces for the perfect fit. (In our case: 30,35,15 or 15,25,30,10 etc.)
2. Fill the time slot with the best fit possible with deviation: (Let's say our time slot is 103 minutes and the deviation is +/-20 minutes. So, we are looking for the best fit anywhere in the 83-123 minute range.
3. Is there any optimizations that can be done if pieces array is sorted?

I'm looking for basic CS algorithms and strategies for optimizing runtime or space. I'm not looking for a specific solution to my problem. Instead, I'm interested in the CS topics I need to look into.

I'm able to solve the simplest version of this problem:
Find out if 2 pieces for the time slot and return true.
Solution:
Loop through the array. Create hashtable and check if hashtable contains  timeslot-pieces[i] if yes, then return true, if no, then add to hashtable.

This is a well known problem in computer science, and can be mentioned as "Find all distinct subset sums in an array". The obvious solution is to generate all subsets which will take O(2^n) time for an array of i elements. Instead, if the sum that you can make is relatively small, you can can use dynamic programming technique to precompute a table which will mark the reached sums. The implementation details of these two ideas can be seen here. Notice that this answers also the second question.

Regarding the third point, whether having a sorted array will allow for further optimizations, the answer is no. If you would've had an applicable greedy solution (taking always the maximum or the minimum element according to some criteria) than it would've been very possible to optimize it somehow, but with simple tests it can be proven that greedy doesn't work in this case. (if it had it would certainly be faster than the dp).


Converting maximization to minimization in aproximation algorithms Suppose algorithm A is given for a maximization problem and we are asked to show that it is a 1/2-approximation algorithm.

As you know it is enough to show

Sol >= 1/2 OPT

What I need to know is, is it true to assume this problem as a minimization one and prove

Sol <= 2 OPT

Or is there any correspondence between these two?

One connection is that maximizing some function $f$ is the same as minimizing its reciprocal $1/f$. You can use this to convert between maximization and minimization.

The general problem of maximizing a function $f$ under some constraints can be very different from the corresponding minimization problem (of the same function $f$). A case in point is MIN-CUT versus MAX-CUT. Whereas MIN-CUT is in P, MAX-CUT is NP-hard to approximate better than some constant.


What is the Inversion Lemma I am taking a programming languages course, and we have had to use the Inversion Lemma many times in our proofs of preservation. We have been given the Inversion Lemma in each of these examples, but is there a general statement of the inversion lemma that can be applied to any proof of preservation? Can someone write that out for me/explain it a little bit?

When you have a collection of rules, an inversion lemma lets you prove the premises of a rule from the conclusion. You can't just assume that inversion is true. You have to prove it by rule induction. However, classes will often give it to you because it is often tedious and easy to prove. The reason inversion doesn't always work is that there may be multiple rules which match the conclusion you are trying to use inversion on, and then you only know that the premises of one of those rules is true, but not which rule.


In flow networks, may source/sink have incoming/outgoing edges? I was wondering. May the source and sink have in-out going edges in a flow-network, and if so - does Ford-Fulkerson and the max-flow min-cut theorem apply ?

Flow-networks are always pictures with no edges entering source, and no edges leaving sink.

I've tried to search the web for an answer, but did not come across an answer i fully understand. Also, I've yet to see a flow network pictured with these edges from source/sink.

Could I transform an undirected graph into a flow-network ? This network will have edges going into source and edges leaving sink ?? This hypothesis is the reason for my question.

Yes, it's possible.

My source is 'Graph Theory and its Applications', 2nd ed, by Gross & Yellen, page 540, question 13.1.8:

  Some authors define an s-t network such that the source s must have indegree 0 and t must have outdegree 0. Describe how a network whose source and sink do not satisfy these additional requirements can be transformed by graphical operations into one whose source and sink do meet such requirements.

However, it doesn't give the construction, I can only think that it would be by adding a supersource and a supersink, as you'd usually do with multiple (though standard) sources and sinks, to 'soak up the leakage'. I am not sure though.


Using saved registers at the main function with no other function calls [RISC-V] The convention when a function is going to use a saved register is to save the contents of that register to the stack in case the caller (if there's one? the main function doesn't have one) had been using this register too and to restore the contents right before returning. Is this convention always obeyed? In the case of a really simple program, with just a main function and no other function calls, would the compiler prefer to optimize and disobey the convention, which means no saving before using the saved register? Of course, a convention is not a rule so i was wondering in which situations can these not be followed?

Calling conventions may be called "convention", but they are rules. The reason they are called "convention" is because each compiler uses a different one, once a convention was chosen - it acts as rules.
Regarding the particular case of "main", it's being called by the operating system, so convention must be obyed.


Prove that the following algorithm has STOP property (number of steps is finite) Prove that the following algorithm has STOP property. I am not sure if this term is widely know, so the definition of STOP property that I got during classes looks as follows:

  STOP property (for all input data satisfying $ \alpha $ the computation halts - the number of steps is finite)

$\alpha: x \in N $

void BB(int x)
{
    int y = x;
    int z = 0;
    while((z != 0) || (y <= 300))
    {
        if(y <= 300)
        {
            y = y + 3;
            z = z + 1;
        }
        else
        {
            y = y - 2;
            z = z - 1;
        }
    }
}

I do not really have any idea how to approach such a problem. I was thinking about using the method of loop counters, but I couldn't success with it.

You have three possible cases:

$y > 300$. Since $z = 0$ initially, the algorithm terminates.
$y = 300$ and $z = 0$.
You enter the first if and you get $y = 303$ and $z = 1$. Then you enter the second if and you get $y = 301$ and $z = 0$. Since $y > 300$ and $z = 0$  the algorithm stops.
$y < 300$ and $z = 0$.
After $k$ iterations $y = 301$ or $y = 302$ or $y=303$ and $z = k$. By executing the algorithm for each $y$ you can see that $y$ only takes values in a specific range while $z$ is always decreasing and will eventually reach 0 (or it will become less than 0). For example, let $y = 301$ and $z = k$. By executing the algorithm you get the following values:

${\bf y = 301, z = k} \\
y = 299, z=k-1 \\
y=302, z = k\\
y = 300, z = k-1 \\
y = 303, z = k \\
{\bf y = 301, z = k-1}\\
y = 299, z = k-2 \\
y=302, z = k-1\\
y = 300, z = k-2 \\
y = 303, z = k-1 \\
{\bf y = 301, z = k-2}\\$

Obviously each time you reach $y = 301$, z is decreased by 1. After showing that the same thing happens for the other two possible values of $y$ you have proved that for every possible starting value, the algorithm stops after a finite number of steps.


Time complexity of computing $AA^T$ What is the time complexity of computing $AA^T$? The context is building a co-citation weighted adjacency matrix.

If $A$ is an $n \times m$ dense matrix then $AA^T$ is an $n\times n$ matrices given by
$$
(AA^T)_{ij} = \sum_{k=1}^m A_{ik} A_{jk}.
$$
This gives a $\Theta(n^2m)$ algorithm for computing $AA^T$.
If $n \geq m$ then faster algorithms exist, but they are not used in practice (at least in most situations).
If $A$ is sparse, that is, stored as a list of non-zero entries, then $AA^T$ can be calculated using different algorithms which exploit the sparsity of $A$. For example, we can sort the non-zero entries in $A$ according to the second coordinate, and then compute $AA^T$ by going over all $k$ and adding $A_{ik} A_{jk}$ to $(AA^T)_{ij}$ for any $i,j$ in the list of $k$. If $s$ is the sparsity of $A$ and $s_k$ is the number of non-zero entries with second coordinate equal to $k$, then this runs in time
$$
\sum_{k=1}^m \binom{s_k+1}{2} \propto \sum_{k=1}^m s_k^2 \in [s^2/m,s^2].
$$
Therefore the worst-case running time is $\Theta(s^2)$, and the best-case running time is $\Theta(s^2/m)$.


How to calculate the complexity of a TM? I have the language

$\{ w \mid w \text{ contains an equal amount of symbols } a \text{ and } b\}$.

I want to show that the language is in the class $\textsf{P}$. To do this, I must give an implementation level description of the relevant Turing machine. I'm not very knowledgeable on Turing machines, but I think I would be able to write down a possible transition function, but from this how do I compute the complexity, in order to show it is in the class $\textsf{P}$?

You only have to show that there exists a Turing machine that decides the language, and such that the number of steps taken by it is a polynomial in the size of the input, in this case a polynomial in $|w|$.

An example of such a machine is the following. Scan the tape left to right until you find both an $a$ and a $b$, and replace both of them with a new symbol, let's say $x$. If you fail to find both an $a$ and a $b$, there are two cases: if every nonblank symbol on the tape is $x$, answer $\textsf{YES}$, otherwise answer $\textsf{NO}$.

It should be easy to see that the number of steps is $O(|w|^2)$, and therefore the language is in $\textsf{P}$.

Just a pedantic note: we usually talk about the complexity of languages or problems, not machines. It would be more appropriate to say "number of steps taken" or "amount of space used" rather than "time complexity" or "space complexity" when talking about a specific Turing machine.


The definition of a graph's transitive reduction I want to determine the transitive reduction of this graph:

as of now, I only found the first step of doing this: represent the transitive closure of the graph as an adjacency relation, so this is what I did:
 (a,b)
 (a,c)
 (a,d)
 (a,e)
 (b,d)
 (c,d)
 (c,e)
 (d,e)

I'm not sure that this is the correct transitive closure of the graph, and I don't know how to move forward in determining its transitive reduction.

If we order the vertices alphabetically, then the adjacency matrix is
$$A=\begin{pmatrix}
0&1&1&1&0\\
0&0&0&1&0\\
0&0&0&1&1\\
0&0&0&0&1\\
0&0&0&0&0
\end{pmatrix}$$
The adjacency matrix of the transitive closure would be
$$B=\begin{pmatrix}
0&1&1&1&1\\
0&0&0&1&1\\
0&0&0&1&1\\
0&0&0&0&1\\
0&0&0&0&0
\end{pmatrix}$$
To get the this one you get each row by navigate the graph starting at the node corresponding to that row and mark with a $1$ the columns of the nodes that you manage to visit and with $0$ the rest.
Now,
$$AB=\begin{pmatrix}
0&0&0&2&3\\
0&0&0&0&1\\
0&0&0&0&1\\
0&0&0&0&0\\
0&0&0&0&0
\end{pmatrix}$$
To build the adjacency matrix $C$ of the transitive reduction put a $1$ in position $(i,j)$ if the $(i,j)$ entry of $A$ is non-zero and the $(i,j)$ entry of $AB$ is zero.
So, the adjacency matrix of the transitive reduction should be
$$C=\begin{pmatrix}
0&1&1&0&0\\
0&0&0&1&0\\
0&0&0&1&0\\
0&0&0&0&1\\
0&0&0&0&0
\end{pmatrix}$$
So, the transitive reduction looks like this


Prove $T$ is a BST iff for every node $x$ of $T$ that is not a leaf, the key of $x$ is larger or equal than the key of the left child of $x$ Let $T$ be a complete binary tree. Prove that $T$ is a binary search tree if and only if for every node $x$ of $T$ that is not a leaf, the key of $x$ is larger or equal than the key of the left child of $x$ or it is less than or equal than the key of the right child.

To prove that if $T$ is BST then for every node $x$ of $T$ that is not a leaf, the key of $x$ is larger or equal than the key of the left child I could say that from the definition of BST it follows that given a node $x$ and a node $y$ which belongs to the left sub-tree of $x$ then $key(y) \le key(x)$.

By the hypothesis if we choose any node $z$ of in the left sub-tree of $y$ then $key(z) \le key(y)$ so the relation holds true for all of the nodes of the tree.

I'm not sure how to approach the proof of the second direction: if for every node $x$ of $T$ that is not a leaf, the key of $x$ is larger or equal than the key of the left child then $T$ is a BST.

The second direction is not always true, in a BST all elements in the right subtree of a node should have a key bigger than its key and all elements in the left subtree of a node should have a key less than its key. for example, consider this binary tree:

     4
   /   \
  2     6
 / \   / \
1   9 3   7

it has the property that for every node x of $T$ that is not a leaf, the key of x is larger or equal than the key of the left child and less or equal than the key of the right child, but it's not a BST since 3 is in the right subtree of root but its key is less than the key of root.


Neural network diverging instead of converging I have implemented a neural network (using CUDA) with 2 layers. (2 Neurons per layer). I'm trying to make it learn 2 simple quadratic polynomial functions using backpropagation.

But instead of converging, it is diverging (the output is becoming infinity)

Here are some more details about what I've tried:

I had set the initial weights to 0, but since it was diverging I have
randomized the initial weights (Range: -0.5 to 0.5)
I read that a neural network might diverge if the learning rate is
too high so I reduced the learning rate to 0.000001
The two functions I am trying to get it to add are: 3 * i + 7 * j+9
and j*j + i*i + 24 (I am giving the layer i and j as input)
I had implemented it as a single layer previously and that could
approximate the polynomial functions better than it is doing now
I am thinking of implementing momentum in this network but I'm not
sure it would help it learn
I am using a linear (as in no) activation function
There is oscillation in the beginning but the output starts diverging
the moment any of weights become greater than 1

I have checked and rechecked my code but there doesn't seem to be any kind of issue with it.

So here's my question: what is going wrong here?

Any pointer will be appreciated.

With neural networks, you always need to randomly initialize your weights to break symmetry.
If you don't use a non-linear activation function in the hidden units, then you might as well have stayed with a single layer. Your network is now just a composition of two linear functions, which is of course just another linear function.
That learning rate seems excessively small. If I'm using a fixed learning rate I normally find a value somewhere between 0.1 and 0.0001 to work well for most problems. This is obviously problem dependent so take my experience for what it is.
In addition to checking your code against the math you've learned, when doing gradient based optimization it can be very helpful to analytically calculate the gradients required using finite differences and compare them to the values you're computing in your code. See here for a discussion of how you can do this. I've caught many errors this way and seeing these types of tests pass always helps me feel much more sure of code correctness.


Can I simplify the recurrence T(n) = 2T((n+1)/2) + c by ignoring the "+1" part? I have written a recurrence relation to describe a recursive algorithm finding the maximum element in an array. The algorthim has an overlap, meaning both of the subarrays that are recurred on contain the middle element of the array.

$T(n) = 2T((n+1)/2) + c$

However, I want to simplify this recurrence relation more.

Since you can often times omit floors and ceilings in recurrence relations, can I omit the $+ 1$?

If so, then my relation is now: $T(n) = 2T(n/2) + c$

Would this alter my big-Theta time complexity? Why or why not?

This probably does not change the asymptotic order.

From $T'(n) = 2 T'(n/2) + c$, you can obtain $T'(n) = \Theta(n)$.

Then you can try to prove that your original $T(n) = \Theta(n)$ by mathematical induction.


Complexity of Search Algorithm I have an algorithm which searches a sorted int array for two elements which sum up to a searched value. First I thought that the complexity is $\mathcal{O}(n)$, but the interpolation search algorithm has a similar approach and has a $\mathcal{O}(\log(log(n)))$ complexity with uniform distributed elements.

Which is the right complexity and why?

boolean hasPairWithSum(int[] elements, int sum) {
    int start = 0;
    int end = elements.length-1;
    while (start < end) {
      int tempSum = elements[start] + elements[end];
      if (tempSum == sum) return true;
      if (tempSum > sum) {
          end--;
      } else {
          start++;
      }
  }
  return false;
}

This method works in linear time, because end - start decreases by 1 on each iteration. It's $n - 1$ initially, hence the loop will make at most $n - 1$ iterations.


Count minimum number of steps to destroy all blocks Given a sequence of integers $A_x$ of length $n$ such that $1 \leq A_x \leq N$,in one step we can remove an element, but when we remove an element we also delete all adjacent numbers which have the same value as the element we remove. We want to count the minimum number of steps to remove all elements.
For example, if our sequence is $[1, 2, 2, 2, 2, 3, 3, 3, 1]$, we can remove it in three steps: firstly we remove the twos, then we remove the threes, and on the end we remove the final two ones.
Our sequence transforms as follow: $[1, 2, 2, 2, 2, 3, 3, 3, 1] \to [1, 3, 3, 3, 1] \to [1, 1]$.
I tried using Dynamic Programming to solve this problem, and my idea was to use $DP[i][j]$ to represent the minimum steps to clear the interval $[i, j]$, however I'm not sure how to work out the transitions, and I'm stuck on the part that there can be some element in the middle of the interval which can be merge with the ends of the interval, and my DP relations cannot handle such cases.

A very similar  problem is the one of clearing the board in an instance of the Two-Dots that only has one column.
This is a single-player game played on a column of colored dots. A move consists of removing a contiguous group of at least two dots that all share the same color and then consolidating all remaining dots.
The goal is to clear the column in the fewest number of moves.
A dynamic programming algorithm for this problem is devised in section 4.2.1 of this paper.  As you suggest $C(i,j)$ is defined as the minimum number of moves needed to clear all (and only) the dots in rows $i$ through $j$.
Your problem has a couple of minor differneces:

A move always deletes a maximal (w.r.t. inclusion) monochromatic group of adjacent dots.
You can also remove a single "dot" if it doesn't match with any neighboring dot.

Here the constraint in 1) can be safely relaxed since it is the case that there is always an optimal solution for the Two-Dots problem that also satisfies such constraint.
To account for 2) you need to redefine $C(i,i) = 1$ (since a single dot can be removed with a single move) and
and, for $i<j$, $C(i,j) = \min \{C_1(i,j), C_2(i,j), 1 + C(i+1,j) \}$ where $C_1$ and $C_2$ are as in the paper and $1 + C(i+1, j)$ considers the case where the first dot is not matched with anything in an optimal solution.


semaphore implementation with test and set I'm trying to understand the algorithm for implementing semaphores on SMP system using test and set instruction described here:
https://people.mpi-sws.org/~druschel/courses/os/lectures/proc4.pdf

(and a bunch of similar implementations on the web).

Locking semaphore looks like this:

void P(Semaphore s)
{
  Disable interrupts;
  while (ldl(s->lock) != 0 k !stc(s->lock, 1));
  if (s->count > 0) {
    s->count -= 1;
    s->lock = 0;
    Enable interrupts;
    return;
  }
  Add(s->q, current thread);
  s->lock = 0;
  sleep(); /* re-dispatch */
  Enable interrupts;
}

I have a number of questions about this.  One is -- what is enabling and disabling of interrupts for?  It seems that the whole reason we are using test and set is that interrupt disasbling is not feasible on SMP systems.
Then, what does the sleep() followed by enable interrupts mean?  Does it mean that we do whole sleep with interrupts disabled?  That can't be right as it defeats the purpose of sleeping.
And if we first enable interrupts and then sleep, doesn't it mean that we have a possibility of missing a wakeup after lock is set to 0 but before we sleep?

The purpose of the spinlock is to prevent other cores from entering the critical section. The purpose of disabling interrupts is to prevent this core from re-entering the critical section.

The only way this core could try to re-acquire the semaphore is if an interrupt occurs and the interrupt handler needs the semaphore for some reason. Disabling interrupts prevents this from occurring.

As for the reason why sleep() is called after releasing the spinlock but before interrupts are enabled... well, that depends too much on the specifics of the operating system design to give a general answer.

The whole of the "waiting on the semaphore" operation should be atomic. That includes waiting on its queue and transitioning the thread from its "running" state to its "waiting" state. Presumably, that's what the call to sleep() is supposed to do.

You wonder if there's a possible race condition where this CPU releases the spinlock on the semaphore, then some other CPU signals the semaphore, then this cpu calls sleep(). That isn't necessarily a problem. If sleep() is written such that if it finds that the current thread is runnable it handles that case correctly, it won't cause a problem.

So why are interrupts disabled when you call sleep()? Some kernels are just designed that way, in that interrupts need to be disabled when you call into the scheduler. The call to sleep() may not actually "sleep"; it might just be whatever the scheduler has to do to make a thread sleep.

Alternatively, if there is a thread context switch hidden deep inside that call to sleep(), that may be where interrupts are re-enabled.

Ultimately, this code is designed to get the general idea across. How you would implement it in a real kernel would be like this, but this isn't necessarily drop-in code.

(Consider that load-linked/store-conditional instructions are spelled out in the example but there's no memory barrier operation on the spinlock release. That's a very specific ISA!)


DFS traversal: explanation required I am studying about DFS these days from the book "Algorithm Design" by Jon Kleinberg. Here a DFS algo is given which is as follows:

DFS(s):
    Initialize S to be a stack with one element s
    While S is not empty
        Take a node u from S
        If Explored[u] = false then
            Set Explored[u] = true;
            For each edge (u,v) incident to u
                Add v to the stack S
            Endfor
        Endif
    Endwhile

Now, how will the following graph be traversed using the above algo?

[TIP] We have to use stack as a data structure

Why I am asking this is because I am confused about the contents of stack at any point of time. I want to see how would you guys do it.

Suppose that vertices are retrieved in alphabetical order, then we'd have:

Iteration

Before stack is modified
stack: [a], visited: []
After stack is modified
stack: [c, b], visited: [a]

Iteration

Before stack is modified
stack: [c, b], visited: [a]
After stack is modified
stack: [f, a, b], visited: [a, c]

Iteration

Before stack is modified
stack: [f, a, b], visited: [a, c]
After stack is modified
stack: [c, a, b], visited: [a, c, f]

Iteration

Before stack is modified
stack: [c, a, b], visited: [a, c, f]
After stack is modified
stack: [a, b], visited: [a, c, f]

Iteration

Before stack is modified
stack: [a, b], visited: [a, c, f]
After stack is modified
stack: [b], visited: [a, c, f]

Iteration

Before stack is modified
stack: [b], visited: [a, c, f]
After stack is modified
stack: [d, e], visited: [a, c, f, b]

Iteration

Before stack is modified
stack: [d, e], visited: [a, c, f, b]
After stack is modified
stack: [b, e, e], visited: [a, c, f, b, d]

Iteration

Before stack is modified
stack: [b, e, e], visited: [a, c, f, b, d]
After stack is modified
stack: [e, e], visited: [a, c, f, b, d]

Iteration

Before stack is modified
stack: [e, e], visited: [a, c, f, b, d]
After stack is modified
stack: [e], visited: [a, c, f, b, d, e]

Iteration

Before stack is modified
stack: [e], visited: [a, c, f, b, d, e]
After stack is modified
stack: [], visited: [a, c, f, b, d, e]

Iteration

Finished

For me, the culprit was to notice that when the algorithm encounters the first element on stack which was already visited, it will not add more vertices to the stack.  This happens in iterations 4, 5, 8, and 10.


Bible Verse division I'm working on a project compiling various versions of the Bible into a dataset. For the most part versions separate verses discreetly. In some versions, however, verses are combined. Instead of verse 16, the marker will say 16-18. I wonder if, given I have a lot of other versions that separate them discretely, I can train an NLP model to separate those combined verses into discrete verses. I'm fairly new at deep learning, having done a few toy projects. I wonder how to think about this problem? What kind of problem is it? I think it might be similar to auto-punctuation problems and it seems the options there are seq2seq and classifier. This makes more sense to me as a classification problem, but maybe my inexperience is what drives me that direction. Can people suggest ways to think about this problem and resources I might use?
In answer to questions in the comment, I am dealing only with text, not images. An example might be like this:
Genesis 2, New Revised Standard Version:

5 when no plant of the field was yet in the earth and no herb of the field had yet sprung up—for the Lord God had not caused it to rain upon the earth, and there was no one to till the ground; 6 but a stream would rise from the earth, and water the whole face of the ground— 7 then the Lord God formed man from the dust of the ground, and breathed into his nostrils the breath of life; and the man became a living being.

Genesis 2, The message version:

5-7 At the time God made Earth and Heaven, before any grasses or shrubs had sprouted from the ground—God hadn’t yet sent rain on Earth, nor was there anyone around to work the ground (the whole Earth was watered by underground springs)—God formed Man out of dirt from the ground and blew into his nostrils the breath of life. The Man came alive—a living soul!

The goal then would be to divide the message version into discrete verses in the way that the NRSV is. Certainly, a part of the guide would be that a verse always ends in some kind of punctuation, though while necessary it is not sufficient to assign a distinct verse.

In my opinion, this may be best approached as a sequence tagging problem, similar to part-of-speech tagging or named entity recognition. (So, this would be the seq2seq option, rather than regular classification). For example, think about it as trying to decide for each token, whether it is the start of a new verse or not.
The advantage of the sequence tagging approach compared to regular classification (at least when using some kind of neural architecture) is that you do not have to predetermine the length of the context taken into account for each distinct tagging decision.
To be clear, the classification approach (e.g, take 20 tokens to the left and 20 tokens to the right and decide whether the middle token is a verse boundary) is also viable, but the sequence tagging approach seems the more natural choice for me.
A final thought on the problem: Are you sure that (any kind of) classification/tagging approach is the right place to start? You may also want to think about this in terms of an alignment problem where you try to figure out which sentences from message edition correspondent to the ones in the NRSV version. Verse segmentation then comes for free. Alignment problems have been studied extensively in statistical machine translation.


Blum's speedup theorem in big-O format? Is there a way to state Blum's speedup theorem in terms of Big-O (Landau) notation?

Blum's speedup theorem implies that for any computable function $f(n,T)$ there is a computable predicate $\Pi$ such that for every program $P_1$ for $\Pi$ there is another program $P_2$ for $\Pi$ whose running time satisfies $f(n,T(P_2)) \leq T(P_1)$. In particular, there exists a computable predicate $\Pi$ such that for every program $P_1$ computing it there is another program $P_2$ computing it and running in time $T(P_2) = o(T(P_1))$.

But the theorem is much stronger: for example, for some other predicate $\Pi$, the guarantee is $T(P_2) = O(\log T(P_1))$; and for another predicate $\Pi$, the guarantee is $T(P_2) = O(T(P_1)/n)$; and so on.


How to apply the Ford Fulkerson algorithm to the assignment problem I am quite familiar with Ford-Fulkerson algorithm but I am having a trouble to apply the algorithm to the following problem. Can someone please give me some hints or better instructions how to use FF method to this problem?
Let O be a set of n objects. It is required to form a set G of m groups. There are three possibly overlapping subsets of objects: A, B and C. Each object belongs to one or more of these subsets. Each object can be assigned to at most one group. It is required that every group must have at least ten objects: two are from subset A, three others are from subset B, and one other is from subset C; the remaining objects can be from any subset.
It is required to explain how to apply the Ford-Fulkerson algorithm to determine whether it is possible to assign n objects to m groups according to the given rules.
Small addendum (See below the idea suggested by @D.W.):
In case of only two subsets A and B, the flow network could look like that (?).
I assume that capacities c1, c2, c3 can be found from subset A and B

I suggest you start with a simpler problem: there are only two (possibly overlapping) subsets, A and B; and every group must have two objects: one from subset A, and one from B.
Once I figured out how to solve that, it was clear to me how to solve your original question.
Hint on how to solve that:

 Have one left vertex per object.  Have two right vertices per group, one to represent which object is chosen from subset A, and one to represent which object is chosen from subset B.  Now figure out how to fill in the edges...


Shortest paths between given red vertices and arbitrary blue vertices Given an undirected weighted graph, where each vertex has one of two colors - red or blue. I have to answer queries to find the shortest path between a given red vertex and any blue vertex in the graph. I have tried using Dijkstra algorithm with source the given red vertex, then finding the shortest path among all shortest paths, but I have to answer many queries for the red vertices and this method proved inefficient. Are there any more efficient algorithms for this problem ?

I assume no negative weights in this solution (since you stated Dijkstra). My solution also uses Dijkstra. Let $G'$ be the graph resulting from $G$ by contracting all the blue vertices into one vertex - which means, remove all blue vertices in the graph and add one blue vertex $b$, and for each edge between a red vertex $u$ and a blue vertex $v$, add an edge between $u$ and $b$.

Claim. A shortest path from a red vertex $u$ to a blue vertex in $G$ has the same length as a short $u$ to $b$ in $G'$.

Proof. Since the graph does not have negative weights, a shortest path can always be replaced with another shortest path with only the last vertex blue (every thing after this vertex are edges with weight 0). Now there is a one-to-one correspondence between shortest paths in both graphs, since inner-vertices on the path can be translated without change and the last edge of the path in $G$ corresponds to an artificial edge to $b$ in $G'$ with the same weight.

Now since the graph is undirected, a shortest path from $u$ to $v$ is a shortest path from $v$ to $u$ (in case of directed graphs we can do this by inverting the graph) and hence, instead of running Dijkstra for each query from a red vertex $v$, run one Dijkstra as preprocessing from $b$ and for each query vertex $v$ answer $d_{G'}(b, v)$.


Converting graphs to sets of paths I have an Euclidean, undirected graph: each vertex is a point on the 2D plane, so the weight of each edge is the Euclidean distance between the vertices.

The number of vertices with no edges is small in comparison to the total number of vertices.
No vertex has more than two edges connected to it.

How can I convert this graph to a closed shape, so each vertex will have exactly two edges connected to it and there will be a path between any two vertices? I want to do it with minimum change in the total weight of all the edges.

This should be NP-hard, here's a way you could try to do a reduction:

Take any graph $G$ embedded in the $\mathbb{R}^2$ plane. Let $c_{min} = \min_{e \in E}\{c(e)\}$  be the minimum edge weight in the graph ($c$ is the weight function of the edges of $G$, i.e. the euclidean distance). To build $G'$, split every vertex $v = (x,y)$ into $v_1 = v$ and $v_2 = (x+\epsilon,y)$ where $\epsilon = \frac{c_{min}}{2^n}$, connect $v_1$ and $v_2$ with an edge weighted by their euclidean distance. Obviously, no vertex in $G'$ is incident with more than two edges, and there are no vertices that are incident with no edges.

What you now would have to prove is something like "there's a TSP route of weight $\le w$ in $G$ iff there's a TSP route of weight $\le w + n \cdot \epsilon$ in $G'$. I don't know how to prove that, but some geometry and use of the triangle inequality might help. I expect the choice of $\epsilon$ as vanishingly small will be enough to give the reduction.

EDIT: The reduction will remain valid after your edit.


Is there an alternative to full factorization for testing the Polya conjecture? The Polya conjecture is a disproved conjecture that states over half the numbers less than any number has an odd number of prime factors. It first fails at $n = 906,150,257$, thus being a good example that testing very many cases is not always enough.

I have been giving "disproving the Polya conjecture" as an exercise a few times, as the counter example is well within computational capabilities.

The simple algorithm for it is to have an incrementing $n$, factorize it, count the factors, and increment either the counter for odd numbers, or even numbers. Continue until you reach the counter example.

Factorization is however an operation to try to avoid, as even the most effective algorithms for that have a nasty computational complexity.

The amount of unnecessary information created by factorizing every number got me wondering if there are better ways. Because:

We do not have to know what the factors of a number are, just how many.
Even the number of prime factors is not needed, as we only need the parity.
We do not have to know the parity of the number of prime factors of each number in a range, it is sufficient to know how many are odd, and how many are even.

Factorization here yields a lot more information than actually needed. Is it really necessary?

You can use a sieve to significantly improve the running time. Decide on a number $N$, say $N = 2^{30}$. Initialize an array of length $N \times 2$ bits: one to keep track of the parity of the number of prime factors, and the second to mark which numbers have been visited. Now run an algorithm similar to the sieve of Eratosthenes. The running time equals the total number of prime factors of all numbers up to $N$, which is roughly $N\log\log N$.

With this information in hand, it is easy to check for violations of the conjecture.


How to detect repeating random numbers? What is the best way to detect repeating sequences of random numbers?

For example, say I got two random number generators (RNG). One of them has been tampered with and is repeating the sequence of random numbers after every N iterations.
The other RNG has not been tampered with and is producing random numbers like it should.

However, one of them is repeating its output every N bytes. N can be small or very large. How to detect this in a reliable and economic way?

Is using rolling hashes (like rsync does) a viable approach?

does not yet seem to be a duplicate on this very site:
cycle detection, see also where hares catch up with turtles
(would-be comment: the question first states repetition every N iterations, next every N bytes.)
(If it didn't carry over: for each PRNG to check, have a clone. For each change in state of the original one, trigger two in the clone. If the states get identical, you detected a cycle. No deterministic PRNG with limited state can avoid it. The states need not be as small as the results; they rarely are, nowadays, and the cycle lengths are huge.)


Compute sums of all subsets of some words We have $16$ words of given length, let's say $W_1,...,W_{16}$ and  and i want to make an one dimensional matrice that will contain all the possible sums of $W_i$'s, for example:

$W_1,W_2,...,W_{16}$

$W_1+W_2,W_1+W_3,...,W_1+W_{16}$

$W_2+W_3,...,W_2+W_{16}$

and so on, all the by two sums...

then all the three sums

$W_1+W_2+W_3,...,W_1+W_2+W_{16}$

then all the four sums

until the sums which is all by sixteen

$W_1+W_2+...+W_{16}$.

Is there a faster way for example, than using a triple $for$ to make all the possible by three sums and in general n fors to make all the by n sums?

If you think that there are much fewer than $2^{16} $ sums, you can try the following approach. Iteratively compute a sorted list of all partial sums of the first $k$ values.  Given this list for some $k$, add to all sums in the list $W_{k+1} $, and then merge the two lists like in Mergesort, removing duplicates. The total complexity should be asymptotic to the number of distinct partial sums.


Algorithm to sort n size input with k distinct elements We need an optimal algorithm in pseudo-code for sorting a sequence of $n$ which has only $k$ distinct numbers ($k$ is not known a Priori).

Can we use Counting Sort to solve this problem in $O(n+k)$ time? I don't think so. Though the time complexity of Counting Sort is $O(n+k)$ but $k$ is the largest element in the input but not the number of distinct elements.

  Is there any chance that we can get a linear time algorithm to solve this problem?

It is not possible. As if $k = \Theta(n)$, Hence you can not find a linear algorithm. Anyhow, you can find an algorithm in $O(n + k\log(k))$.

Find maximum in $O(n)$. Then create a hash table to find the $k$ distinct values is $O(n)$. Then sort the $k$ values in $O(k\log(k))$. Notice that the space complexity in this algorithm is $O(\text{largest value})$. However, the time complexity would be $O(n + k\log(k))$.


Compress 32 bit integer into a normalized float and sorry if this is a duplicate of some sort, my poor technical vocabulary doesn't get me very far with google.

I am trying to implement some well-known PRNG algorithms. For the time, the algorithm in themselves do their job very well (generating 16/32/64/128 random bits). I am now trying to create a uniform distribution function, that, taking as input a 16/32/64/128 bit integer spits a IEEE compliant binary2, binary4 or binary8 (the function doesn't have to handle all of them at once, but by able to somewhat template for the other floating point types.

As quoted in the title of the question, the output shall be between -1.0 and 1.0 . A naive implementaion would be to take a byte of the integers, and affect it to the exponent, while leaving the rest to the mantissa (padding with 0s if there's not enough bits), but how to handle denormals (the code is performance critical, and the target is reluctant with un-uniform data-based condition). How to handle these then ?.

And while that may be asking two questions at once, how to do the same for a normal distribution ?

Any help or guidance is appreciated. Thanks in advance

You can avoid getting denormals by truncating the number of random bits to ensure that there are none; even if you don't do that, the probability of getting a denormal is extremely small.

The standard way to convert uniform random variables to Gaussians is the Box–Muller transform.