Confusion in the solution to first readers-writers synchronization I am studying the solution to “First Readers-Writers Problem” from the book Operating System Concepts (9th edition) and it describes:

  First readers–writers problem, requires that no reader be kept waiting unless a writer has already obtained permission to use the shared object. In other words, no reader should wait for other readers to finish simply because a writer is waiting.

And what I have understood from this is that if there is any reader running and a writer comes, then that writer would be blocked until reader has completed. But during the completion of the first reader, if there comes another reader (or multiple readers), then that (those) reader(s) will be given priority over the writer.

First of all please correct me if I am wrong here. But if am right, then what I have understood is that, the code for  the reader below does not guarantee this.

Code for reader-writer is given below:

//data structures
semaphore rw_mutex = 1;
semaphore mutex = 1;
int read_count = 0;

//Code for writer
do {
   wait(rw_mutex);
   . . .
   /* writing is performed */
   . . .
   signal(rw_mutex);
} while (true);

//Code for reader
do {
   wait(mutex);            //Line 01
   read_count++;

   if (read_count == 1)
      wait(rw_mutex);      //Line 02

   signal(mutex);
   . . .
   /* reading is performed */
   . . .

   wait(mutex);            //Line 03
   read_count--;

   if (read_count == 0)
      signal(rw_mutex);    //Line 04

   signal(mutex);
} while (true);

Now suppose following sequence of events occurs:

Suppose a first reader comes and it blocks the writer on the line mentioned as Line 02 in comments.
Then a writer comes which is waiting for rw_mutex.
Then the first reader is executing the code line mentioned as Line 03 in comments and it has locked the mutex semaphore.
At the same time a second reader comes and it starts waiting on the line mentioned as Line 01 in comments.
Now when the first reader executes Line 04, it releases the lock on rw_mutex and the writer which was waiting in its while loop is unlocked now and starts executing.
The second reader will be unlocked when the first reader executes the line after Line 04 that signals the mutex semaphore.

Now if we see the overall flow, then the writer runs before the second reader. So does the code logic work the same as described above?

Please correct me if I am wrong.

But during the completion of the first reader, if there comes another reader (or multiple readers), then that (those) reader(s) will be given priority over the writer.

It's a bit more subtle. The second reader is not given priority. Rather, the reader is not blocked by the first reader. This means that if the first reader takes sufficiently long, then the second reader will eventually start reading, even if there is also a writer waiting to take the lock. It is possible however to have a sequence of events where:

A first reader is reading.
The first reader has finished its task and starts releasing the reader-writer lock. This is not an atomic operation: the first reader needs to perform several operations (decrement read_count, test it for zero, and call signal on rw_mutex), and these operations must look atomic from other processes' point of view so they are performed in a critical section, protected by mutex. Thus “starts releasing the reader-writer lock” means “takes mutex”.
A second reader enters the system and starts working on acquiring the reader-writer lock, but it has not yet finished acquiring the reader-writer lock. The second reader waits on mutex, which is currently held by the first reader.
A writer enters the system and starts working on acquiring the reader-writer lock: it waits on rw_mutex.
The first reader is releasing the reader-writer lock, and it signals rw_mutex, allowing the writer to take it.

This sequence of events is what is going on in the scenario you describe: the second reader is waiting at line 01, and the first reader goes through line 03 then line 04.

In typical operation, this scenario will not occur often, because it depends on the second reader starting to wait on mutex while the first reader holds it. Given that the first reader only keeps that semaphore for a very short time, this scheduling is unlikely: most of the time, mutex is not held.

If the second reader arrives (i.e. calls wait(mutex)) before the first reader enters the critical section to release the reader-writer lock, then the second reader can start reading while the first reader is still reading, and the writer only gets the reader-writer lock once the second reader has finished. If the second reader arrives after the first reader exits that critical section, then it is clear that the already-waiting writer will grab the lock first. It's only if the second reader arrives during the first reader's critical section that there is this possibility of inversion where the writer arrives after the second reader, while the first reader is still in the critical section, and then the writer wins the race.

This kind of rarely-occurring scenario is an illustration of why concurrency is difficult. It's rare, but you still need to make sure your algorithm works in this case, because when it does occur, if your algorithm is buggy, it can bring your system down in a way that's hard to identify and fix. Here, this scenario specifically illustrates the need for mutex: without it, the second reader and the writer could both take the reader-writer lock.

In situations with low contention (i.e. it's rare that multiple processes want the same lock at the same time), as long as your algorithm is correct, the fact that the writer sneaks past the second reader is irrelevant. In situations with high contention, this kind of inversion can lead to starvation, and sometimes more sophisticated algorithm ensuring some kind of fairness property are needed.


Delta formal definition for DFA How can I formally define * for a dfa with multiple initial states?
I know that the δ formal definition for NFA is δ: Q × ∑ → 2^Q
and for DFA it's δ : Q × Σ → Q
but what should I do if there is multiple initial states?How can I take into consideration all the options for the initial state?It seem like it should combine the NFA definition and DFA definition.. δ: 2^Q × ∑ → Q maybe?but it doesn't seem right neither.

I would appreciate any help I can get on this matter

If you have multiple initial states, then this automata is non-deterministic.


Finding missing edge weights in the context of minimum spanning tree I came across following problem:

  Problem 1
  Suppose that minimum spanning tree of the following edge weighted graph contains the edges with weights $x$ and $z$, then what are $x$ and $z$?

The solution given was as follows:

  There are two ways to reach node $F$, one from node $A$, other from node $G$. Maximum weight of the edge in MST is smallest of two. Hence 11.
  Similarly there are four edges incident on node $B$, having weights $13,14,8,z$. If $z$ is included in MST, then it should be at least $min(13,14,8)$, that is 8.

Then I came across another problem:

  Problem 2
  In below graph, the edge weights of only those edges which are in the MST are given. What are the weights of other edges?

Solution was:

  In every cycle, the weight of an edge that is not part of MST must by greater than or equal to weights of other edges which are part of MST. Since all edge weights are distinct, the weight must be greater. So $w(ED)=6, w(CD)=15$
   and $w(AB)=9$

First solution chooses min degree of a node, whereas second solution chooses max edge weight in cycle. This seems to be obvious since first problem has "unknown MST edge weights", whereas second problem have "unknown non-MST edge weights".

But, I have several doubts here:

In solution 1, why we examine edges incident on node $B$ only, but not node $C$? I guessed following procedure:

  If we start preparing MST using Kruskal's algorithm, we will go on adding edges in sequence $AG,IJ,CD,...$ and $C$ gets connected to MST. So in this particular example, it works by preparing MST using the known edge weights such that the edges chosen wont change whatever the unknown weights turn out to be. And then based upon vertices connected to the MST prepared so far, decide which of the vertices of unknown weight edge is to be reached by  that edge.

Is this procedure correct? Does it work in all cases / graphs? Is there any other standard approach to solve such problem?
Second solution used cycle $E-D-F-E$ to determine the weight of edge $ED$, but not cycle $B-E-D-C$. Though I understand that decision of choosing $EF$ and $DF$ are dependent on $ED$, doesnt decision of selecting $BE$ is dependent on total of weights of $CD$ and $ED$? What is exact rule/idea for deciding which cycle to consider while determining non MST edge weight?
Is there some standard well defined steps for both problems? Or its more sort of trial and error work?

Firstly, to make the nice answer given by OP to Problem 1 the only valid answer, we should change its question "what are $x$ and $z$?" to "what are the maximal weights of $x$ and $z$?". Otherwise, we can have many valid answers such as "$x=3, z = 5".
Secondly, to make the nice answer given by OP to Problem 2 the only valid answer, we should change its question "What are the weights of other edges?" to "What are the minimal weights of other edges?". Otherwise, we can have many valid answers such as "$w(ED)=16, w(CD)=115$ and $w(AB)=19$".
Lastly and most importantly, let us answer the central question, "Is there some standard well defined steps for both problems? Or its more sort of trial and error work?". A standard way to rephrase the question is, "Is there an effective algorithm for both kinds of problems?"
Let $G$ be an edge-weighted connected undirected graph with some unknown weights. Let us state the questions clearly in more detail. We will assume there are graphs that satisfy the given conditions in the problems. (Otherwise, we can add extra steps to the algorithms below to detect those impossible situations).
The first kind of problem: unknown weights in an MST

Assume that we know a minimum spanning tree (MST) of $G$ such that all edges of unknown weights belong to that MST. What are the maximal values of those unknown weights?

Here is the sketch of an effective algorithm, which can be considered as a precise abstraction of OP's concrete solving procedure.
Pick any edge $e$ that is not that MST. If we add $e$ to that MST, we will create a unique simple cycle. All edges of MST in this cycle must be as light as or lighter than $e$. Collect these inequalities, all of which have the form "$x\leq a$" where $x$ is the unknown weight of some edge in that MST and $a$ is a known number. Repeat until we have gone through all edges that are not in that MST.
Now we have a collection of inequalities about some unknowns and numbers. Remove redundant inequalities. Find an inequality "$x\leq a$" with the smallest number $a$ where $x$ is an unknown. Let $x=a$  be part of the answer. Repeat this process until we have no more inequalities.
The second kind of problem: unknown weights outside an MST

Assume that we know a minimum spanning tree (MST) of $G$ such that all weights of edges of the MST are known. What are the minimal values of the  unknown weights?

Here is the sketch of an effective algorithm, which can be considered as a precise abstraction of OP's concrete solving procedure.
Pick any edge $e$ of unknown weight. If we add $e$ to that MST, we will create a unique simple cycle. All edges of MST in this cycle must be as light as or lighter than $e$. Collect these inequalities, all of which have the form "$a\leq x$" where $x$ is the unknown weight of $e$ and $a$ is a known number. Repeat until we have gone through all such edge $e$ of unknown weight.
Now we have a collection of inequalities about some unknowns and numbers. Remove redundant inequalities. Find an inequality "$a\leq x$" with the largest number $a$ where $x$ is an unknown. Let $x=a$ be part of the answer. Repeat this process until we have no more inequalities.
More general problems?
If you have read this far, it will be obvious that we could create more general problems of similar kinds. We will have a general approach towards producing an algorithm as well. So much for my answer that is already long.


Find the median of a list of sorted arrays Input:
A set of $\ell$ arrays $A_i$ (of numbers).

The elements within each array are in sorted order, but the set of arrays is not necessarily sorted. The arrays are not necessarily the same size. The total number of elements is $n$.

Output:
The $k$th smallest element out of all elements in the input.

What's the most efficient algorithm for this problem?

Is it possible, for example to achieve a running time of $O(\ell + \log n)$?

You can do it in $O(l + k \text{ log } l)$ time and $O(l)$ extra space as follows:

Build a binary heap with one entry for each of the arrays.  The key for entry $i$ is the smallest element in array $A_i$.  This takes $O(l)$ time.
Select the smallest entry from the heap and remove it (taking $O(\text{log } l$) time).  Add that entry back to the heap using the next smallest entry in the relevant array as its key (again $O(\text{log } l)$ time).
Do the previous step $k$ times.  The last element you remove from the heap is your answer.

If you replace the binary heap with a Fibonacci heap, I think this gets you down to amortized $O(l + k)$ time, but in practice it'll be slower than the binary heap unless $l$ is HUGE.

I suspect that the Fibonacci heap bound is optimal, because intuitively you're going to have to inspect at least $k$ elements to find the $k$th smallest one, and you're going to have to inspect at least one element from each of the $l$ arrays since you don't know how they're sorted, which immediately gives a lower bound of $\Omega(\text{max}(k, l)) = \Omega(k + l)$.


Time Complexity of Regular Languages I wonder how I can go about proving that if a language L is decidable in o(nlog(n)) then L must be regular.

I should probably mention that by "decidable" I mean "being decidable by single-tape deterministic turing machine".

Thanks and regards
Guillermo

This is a classical result of Kobayashi, On the structure of one-tape nondeterministic Turing machine time hierarchy, Theorem 3.3 on page 188. The idea is to use crossing sequences: you show an upper bound $O(1)$ on the size of any crossing sequence, and then use an argument of Hennie, One-tape off-line Turing machine computations, Theorem 2 on page 561, to conclude that the language accepted by the machine is regular.


What publication first introduced the concept of a non-deterministic Turing machine? What publication first introduced the concept of a non-deterministic Turing machine?

Turing did not define the concept in his 1936 paper.

This will be a partially inconclusive answer, unfortunately. Hopefully someone more knowledgeable can chime in and confirm the missing details. Let me summarize what I could find out so far.

Nondeterministic automata were introduced by Rabin and Scott in 1959. They also define two-way automata (which is a prelude to the LBAs introduced by Myhill the following year), but I could not find any mention of a nondeterministic two-way automaton (let alone a Turing machine) there.

The next paper (in chronological order) in which both nondeterminism and Turing machines appear is "On computability by certain classes of restricted Turing machines" by Fischer, 1963. In it, he defines general machines and also allow them to be nondeterministic. However, in the proof of Theorem 5 there he curiously states that some results (regarding deterministic and nondeterministic machines) are "well-known" to be equivalent for Turing machines. Hence, one is lead to believe the notion must have arisen sometime between the Rabin and Scott paper and Fischer's paper in 1963. Fortunately, Fischer gives a clue as to where he has those results from:

  The author is indebted to Dr. J. Evey for many of the ideas contained herein. He has worked closely with the author in this area and, in particular, is responsible for the results constituting parts (c) and (d)
  of Theorem 3 and for the main construction in part (e).

Theorem 3 in case is the computational equivalence of DTMs and NTMs.

Indeed, roughly a month after Fischer's paper Evey published "Application of pushdown-store machines," in which we also find nondeterminism applied to general machines (including Turing machines), and in which he proves the result that Fischer mentions (and extending it to some other types of machines). Fischer's work is actually listed in the bibliography there as well, but as far as I can tell there is no explicit citation of it in the text. The paper is most likely a summary of Evey's doctoral thesis (similarly titled), but I could not find it online; maybe someone with access to it can confirm that.

What I conclude then is that, unless I have made a gross oversight somewhere, the notion of an NTM must have just been evident to the research community once Rabin and Scott had brought nondeterminism to the table. Evey deserves credit for proving the computational equivalence of DTMs and NTMs, but it is hard to tell from the evidence at hand if he was the first to mention NTMs as a concept too (possibly in his doctoral thesis).


Assuming P != NP, what is the cardinality of the set of NP-Hard languages? If P=NP, then every non-trivial language is NP-Hard, so clearly there are uncountably many NP-Hard languages. However it's less clear to me what the cardinality of this set is assuming P != NP.

Any upwards-closed non-empty class $\mathfrak{L}$ of languages has the cardinality of the continuum, with very few limitations on what kind of reasonable reducibility we are looking at. The reason is if $A \in \mathfrak{L}$ and $B$ is an arbitrary language, then the language $A + B = \{0w \mid w \in A\} \cup \{1w \mid w \in B\}$ satisfies that $A \leq A + B$, hence $A + B \in \mathfrak{L}$. Since $A + B = A + C$ iff $B = C$, we see that $B \mapsto A + B$ provides an injection from the all languages into $\mathfrak{L}$.


How do you convert bits into a different alphabet? I have forgotten how to do this. How do I figure out what the requirements are for a 128-bit string using a certain alphabet?
That is to say, I want to generate a UUID (128-bit) value, using only the 10 numbers for the alphabet. How many numbers do I need, and what is the general equation so I can figure this out for any alphabet of any size?
What is the equation for any n-bit value with any x-letter alphabet?
The way I do it is to guess and slowly iterate until I arrive at a close number. For powers of 10 it's easy:
Math.pow(2, 128)
3.402823669209385e+38
Math.pow(10, 39)
1e+39

For other numbers, it takes a little more guessing. Would love to know the equation for this.

To estimate the number of decimal digits needed to represent a $128$ bit number you use logarithms to base $10$:
$128 \times \log_{10}(2) \approx 38.53$
so you need $39$ decimal digits to represent a $128$ bit number.
In a general, for an “alphabet” with $n$ symbols you need to find the value of $128 \times \log_n (2)$ and then round this up to the next whole number.


Maximizing product of list of integers whose sum equals n Given a positive integer n, find the list of positive integers whose product is the largest among all the list whose sum is n. For example, if n is 4 the desired list is 2, 2 because 2x2 = 4 is larger than 1x1x1x1 = 1, 2x1x1 = 2 and 3x1 = 3, if n is 5, the desired list is 2, 3.
What is the desired list if n = 2001?
Actually, what is an algorithm to generate this list? After tried lots of examples, I discern (hope am right) for n > 5 it's a list of 3's, and a remainder n % 3.
So, for n = 2001, I got a list of 667 3's.
Question
If Correct, what property of 3 makes it the ideal integer in that it composes (mostly) this list?.

Intuitively the function $(n/x)^x$ is maximized at $x=\frac{n}{e}$ and 3 is closest to $e$.


Is this some kind of hashing? Say I have $n$ vectors $\{ z_i \in \mathbb{R}^D\}_{i=1}^n$ (where $n$ is very large and hence I can't do any calculation which scales as $n$) and I want to create $n$ vectors $\{x_i \in \mathbb{R}^d \}_{i=1}^n$ with $d$ as small as possible, such that $\forall i,j <z_i,z_j>$ is either very close to $<x_i,x_j>$ OR w.h.p $  <z_i,z_j> = <x_i,x_j>$.

Is there a standard answer known for this - by maybe using hashing?
One possible way might be to either deterministically or randomly from some distribution pick some $D-d$ coordinates and drop those coordinates from each $x_i$ to get the corresponding $z_i$ such that for each pair on either side either the inner-product is well approximated or is equal with high-probability over the way the coordinates are sampled. Is such a way of sampling known?

For the second option one other way to think would be to pick an unit magnitude gaussian vector at random $g \in \mathbb{R}^d \subset \mathbb{R}^D$ and to define $x_i$ as the projection of $z_i$ along $g$. Then indeed one has that $\mathbb{E}_g[ <x_i,x_j>] = <z_i,z_j>$.

But can this above be shown to be true with high concentration or be derandomized?

I think your "possible way" is a known variant of "locality sensitive hashing", which is what you're looking for, I suspect.


Algorithm for calculating regular divisions of lengths in easy-to-read form I am creating some charts for elevation v distance data.

The original source of the data is GPX files and from them I have extracted...

The total route distance (km) and each point along the route as [lat, long, elevation, distFromStart]

The chart plots distanceFromStart (X-axis) v elevation (Y-axis).

The routes can be anything of length between 0.5km and 450km.

The issue I have is with calculating the divisions (the tick values) for the x-axis of the graph. The tick values should always be easy to read, rounded values. The number of ticks is flexible from 5 - 12 (or thereabouts).

So given

A distance (in km)
A list of acceptable tick values (0.1km, 0.2km,
    0.5km, 1km, 2km, 5km, 10km, 20km, 50km)

How can I calculate which acceptable tick value I should use and the number of ticks on the x-axis?

I would shoot for having about the same number of ticks each time, given that the tick values are acceptable. I am interpreting tick values as the constant difference between two tick values. Say you wanted to have about $n$ ticks and you are given a distance $d$. Then your tick values would be about $\frac{d}{n}$. Round this up or down to the nearest acceptable tick value.


The space complexity of recognising Watson-Crick palindromes I have the following algorithmic problem:

  Determine the space Turing complexity of recognizing DNA strings that are Watson-Crick palindromes.

Watson-Crick palindromes are strings whose reversed complement is the original string. The complement is defined letter-wise, inspired by DNA: A is the complement of T and C is the complement of G. A simple example for a WC-palindrome is ACGT.

I've come up with two ways of solving this.

One requires $\mathcal{O}(n)$ space.

Once the machine is done reading the input. The input tape must be copied to the work tape in reverse order.
The machine will then read the input and work tapes from the left and compare each entry to verify the cell in the work tape is the compliment of the cell in the input. This requires $\mathcal{O}(n)$ space.

The other requires $\mathcal{O}(\log n)$ space.

While reading the input. Count the number of entries on the input tape.
When the input tape is done reading

copy the complement of the letter onto the work tape
copy the letter L to the end of the work tape

(Loop point)If the counter = 0, clear the worktape and write yes, then halt
If the input tape reads L

Move the input head to the left by the number of times indicated by the counter  (requires a second counter)

If the input tape reads R

Move the input head to the right by the number of times indicated by the counter (requires a second counter)

If the cell that holds the value on the worktape matches the current cell on the input tape

decrement the counter by two
Move one to the left or right depending if R or L is on the worktape respectively
copy the Complement of L or R to the worktape in place of the current L or R
continue the loop

If values dont match, clear the worktape and write no, then halt

This comes out to about $2\log n+2$ space for storing both counters, the current complement, and the value L or R.

My issue

The first one requires both linear time and space. The second one requires $\frac{n^2}{2}$ time and $\log n$ space. I was given the problem from the quote and came up with these two approaches, but I don't know which one to go with. I just need to give the space complexity of the problem.

The reason I'm confused

I would tend to say the second one is the best option since it's better in terms of time, but that answer only comes from me getting lucky and coming up with an algorithm. It seems like if I want to give the space complexity of something, it wouldn't require luck in coming up with the right algorithm. Am I missing something? Should I even be coming up with a solution to the problem to answer the space complexity?

Disclaimer: The following algorithm does not use the standard model for sublinear space complexity (see WP:DSPACE), because it writes to the input tape. Furthermore the set of (Watson-Crick) palindromes is not in $\mathsf{DSPACE}(\mathcal{O}(1)) = \mathsf{REG}$. Nevertheless, it's an in-place solution for many practical purposes (e.g. if each letter is a char in C).

To show that a problem has a specific space complexity, one generally needs to come up with an algorithm that has that space complexity. This may require trial and error, but a better approach is to have a good understanding of the problem you are looking at and a good amount of experience in algorithms and complexity.

For this particular example, there is a third algorithm that does not need any additional space and requires $O(n^2)$ time complexity. This algorithm would be constant space.

Hint: why use additional space, when you can use the space occupied by the input?

Hint: zip back-and-forth across the string checking one character at a time – use the state of the Turing Machine to remember which character you are checking and erase characters you've already checked.


How to partition disagreeable people into compatible groups We have a number of people that must be partitioned into groups, but there may be people that dislike other individuals.   Partition the people into the minimum number of groups such that no person is grouped with someone they don't like.  (If A doesn't like B then A cannot be in a group with B. Each person must belong to exactly one group.)

The incompatibilities between people are given explicitly as unordered pairs of people that cannot be in a group together.

Consider one possible scenario involving 10 people where incompatibility pairs are given as follows:

(1,2) (1,6) (1,7) (2,3) (2,6) (2,7) (2,8) (3,4) (3,7) (3,8) (3,9)
(4,5) (4,8) (4,9) (4,10) (5,9) (5,10) (6,7) (7,8) (8,9) (9,10)

In this scenario it is unacceptable to form a group consisting of persons [ 1, 4, 5 ] because of the incompatibility pair (4,5), which means that persons 4 & 5 are incompatible and cannot be in the same group.

For the scenario given above, we can divide people up optimally into groups that all get along, using no fewer than 4 groups.  Here is one such way of arranging people into 4 groups.

GROUP #1 : [ 1, 3, 5 ]
GROUP #2 : [ 2, 4 ]
GROUP #3 : [ 6, 8, 10 ]
GROUP #4 : [ 7, 9 ]

Note, that the groups do not have to have the same number of members, and it is acceptable to have a group consisting of only one individual if necessary.  But each person must assigned to a group.

Describe an algorithm, given an arbitrary incompatibility matrix among N people in the form of zero or more incompatibility pairs, to determine a compatible grouping that uses the fewest groups possible.

EDIT:  Here's what I have tried so far.

A greedy algorithm:

While there are persons not yet assigned to a group.
   Take the lowest numbered unassigned person and create a new group `g` consisting of just them.
   For each person `p` not yet added to a group:
       If they are not incompatible with anyone in the current group `g`:
          Add person `p` to group `g`

I have no confidence at all that this would produce the minimal number of groups though.

You are essentially asking this:
"Given a graph $G=(V,E)$ where each vertex in $V$ denotes a person and each edge $(u,v) \in E$ means that $u$ is incompatible with $v$, what is the minimum number of colors required to color the vertices of $V$ such that no edge in $E$ has both endpoints of the same color?"

In other words, given any graph $G$ (which can always be realized with a suitable set of incompatibilities), find the chromatic number $\chi(G)$ of $G$.

This is a well-known NP-hard problem. In particular, it is already NP-hard to decide whether $\chi(G) \le 3$.
For the special case of $2$ colors, $\chi(G) \le 2$ can be decided in linear time (just check whether $G$ is bipartite, which also gives you the corresponding coloring if that is the case).

However, since you are just asking for an algorithm (no mention of a polynomial-time complexity or even efficiency) you might as well enumerate all existing colorings in $O(3^{|V|} + \dots + \chi(G)^{|V|}) = O(\chi(G)^{|V|})$ time.
This can be improved to $O(2.2461^{|V|} )$ time, see:
https://epubs.siam.org/doi/10.1137/070683933

Finally, there is simple linear-time greedy algorithm that uses at most $\Delta(G)+1$ colors, where $\Delta(G)$ is the maximum degree of $G$: Examine the vertices of $G$ one at a time, color a vertex with any color that is not already used by any of its neighbors.

This is the relevant Wikipedia page: https://en.wikipedia.org/wiki/Graph_coloring .

EDIT

Your algorithm is iteratively computing maximal independent sets of $G$. Similarly to the greedy algorithm, it will return a coloring with at most $\Delta(G)+1$ colors.
To see this, suppose that there is a vertex $v$ of color (group) $\Delta(G)+2$. Then, since $v$ has not been added to any of the first $\Delta(G)+1$ groups, it must have at least one neighbor in each of those groups. This means that the degree of $v$ is at least $\Delta(G)+1$, a contradiction.

Here is a tight example for both algorithms (vertices are examined in increasing order of their label):


Finding asymptotically tight bounds $\Theta$ of two procedures I would like to check time complexity of two procedures for which I am not totally convinced that I got it right. Now the first procedure is this:

public static int c(int n) {
    int i, j, s = 0;
    if (n > 1) {
        for(i = 0; i < n; i*=2) {
            for(j = n; j > 0; j/=2) {
                s++;
            }
            s+=c(n-2);
        }
    }
}

Now I have set the following recurrence equation:
$T(n)=\log_2n*T(n-2)+\Theta(\log_2n)$

Now the height of the recurrence tree is $n/2$ so the $T(n) = n/2 * (\log_2n+\log_2n)=\Theta(n*\log_2n)$

The next procedure is this:

public static int d(int n, int m) {
    int i, j, k, ss = 0;
    if (n > 1) {
        for(i = 0; i < n; i++) {
            for(j = i; j > n; j+=2) {
                ss+=(i+1)-2*j+m;
            }
        }
        for(k=0; k<8; k++) {
            ss+=d(n/2, m/(k+1))
        }
    }
    return ss;
}

Again I have set this equation:
$T(n, m)=8*T(n/2, m/(k+1))+\Theta(n^2)$

Now I think the $m$ parameter is not important because it is not used in for loop as a counter. Where $n/2$ gives us a recurrence tree of height $\log_2n$. So we get this:
$T(n, m) = 8 * \log_2n*n^2=\Theta(n^2)$

I know that recurrence equations that I have set up are probably right, while the I am not sure about next steps.

Note that the first algorithm never terminates for $n>1$; it starts with $i=0$
and multiplies $i$ by $2$ in every iteration of the outer loop, so we never get
$i \geq n$. I'll assume we start with $i=1$ instead.

I have some problems with your approach.

What are you counting? Why?
Where do the $\Theta$-terms in the recurrences come from? Don't you know better?
Your $\Theta$-"arithmetic" is flawed. Please check your definitions and maybe our related reference questions.

To give you something to work with, let's look at your first algorithm. I say we count arithmetic operations and comparisons because they seem to be the most numerous (no other operations occur in the inner loop). Each loop translates to a sum, so we get

$\qquad\displaystyle T_c(n) = \sum_{i=0}^{\lfloor \log_2(n) \rfloor} 4 + T_c(n-2) + \sum_{j=0}^{\lceil \log_2(n) \rceil} 3$

and $T_c(0) = T_c(1) = 0$. You have to solve this recurrence; note that it contains a bit more detail than yours. If you throw such detail away, you should be very certain that this is justified (which is why professors do it all the time when appropriate). Such certainty comes only with practice, so you should work a few cases through rigorously.

First, you should simplify the sums. For the purpose of obtaining $\Theta$-bounds, you can work with upper and lower bounds on the recurrence. For instance, consider

$\qquad\displaystyle T_c^\leq(n) = (\log_2(n) + 1) \cdot (4 + T_c^\leq(n-2) + 3(\log_2(n) + 2))$ and

$\qquad\displaystyle T_c^\geq(n) = (\log_2(n) - 1) \cdot (4 + T_c^\geq(n-2) + 3\log_2(n))$

with the same anchors. If you get the same $\Theta$-bounds (or compatible $O$- and $\Omega$-bounds) from these, you have by $T_c^\geq(n) \leq T_c(n) \leq T_c^\leq(n)$ and squeeze theorem a $\Theta$-bound for your original recurrence.

Strategies for solving recurrences are already exhibited in detail in our reference question, so I'll leave that part to you.


How can I get index of combination from element indices An array of combinations is generated from two arrays,
               indices:  0   1   2   3   4   5
               array 1: [a,  b]
               array 2: [A,  B,  C]
     repeating array 1:  a,  b,  a,  b,  a,  b
     repeating array 2:   A,  B,  C,  A,  B,  C
          combinations: [aA, bB, aC, bA, aB, bC]    length = LCM(2, 3)

INPUT : a, C
OUTPUT: 2, which the index of aC in the generated combinations.

Say, when a and C are given whose indices are already known as 0 and 2 in the original arrays, how to find the index of aC, which is 2? Is there any algorithmic way to do this?
For detailed background information, please check version 1 of this question.

(BTW, I think the code in the first edition of the question was the issue -- not the background info with respect to the sexagenary cycle, which is actually good to include to understand the motivation for the problem).
To put the problem a bit differently, you have the sets $\mathbb{Z}/m\mathbb{Z}$ =  $\{0,1,...,m-1\}$ and $\mathbb{Z}/n\mathbb{Z} = \{0,1,...,n-1\}$, and you start with the pair (0,0), then (1,1), etc., basically applying the mapping $(x,y)\mapsto(x+1 \mod m,y+1 \mod n)$, until you wrap back around to $(0,0)$. In the easy case where $m=n$ then, you can see that $(i,i)$ was the $i$-th term in the sequence  (0-based). In general, if you are asking about the index of $(i,j)$, then you are effectively trying to solve the system of congruences
\begin{align*}
x &\equiv i \mod m \\
x &\equiv j \mod n
\end{align*}
for $x$. Here $x$ represents how many times you did the $(+1,+1)$ operation starting with $(0,0)$.
When $m$ and $n$ are coprime, the Chinese remainder theorem gives you an algorithm to compute the solution.  When they are not coprime, then that system in general may not have a solution, but in the case where the system was created by the above construction, it does. This math.stackexchange answer shows you how to find the (unique) solution in the range $[0,LCM(m,n))$.


Treewidth of k x k square grid graphs According to some slides I found on google, the treewidth of any $k \times k$ square grid graph $G$ is $tw(G) = k$. I just started researching about treewidth and tree decomposition, and for the most part it makes sense. However, I am particularly interested in the $k \times k$ square grid graph case, but have been struggling on how it is possible to make a tree decomposition of such a graph with that low of a width.

One of the problems I run into when trying to draw out decomposition trees of small square grids with groups of at most $k+1$ (to ensure a decomposition tree where the width is $k$) is that since the graph is "cyclic", one of the corner nodes shows up in two opposite ends of the tree, but not in any nodes on the path between the two. This clearly violates the coherence property of decomposition trees, which according to Wikipedia (which gives a more precise definition than most) is:

  If $X_{i}$, $X_{j}$, and $X_{k}$ are nodes (in the decomposition
  tree), and $X_{k}$ is on the path from $X_{i}$ to $X_{j}$, then
  $X_{i}\cap X_{j}\subseteq X_{k}$.

For the case of the $3 \times 3$ graph, the only valid (or at least what I believe to be valid) decomposition tree I can think of contains 2 nodes: $\{\{1, 2, 3, 4, 6, 7, 8, 9\}, \{2, 4, 5, 6, 8\}\}$ where the nodes are labeled by row starting from the top left corner:

$1\space2\space3$

$4\space5\space6$

$7\space8\space9$

I did this by taking the perimeter vertices for the first tree node, and the inner vertex ($5$) along with its adjacent vertices to ensure all edges and vertices are included.

Ultimately, my question is, how can the treewidth of a square $k \times k$ square grid graph actually be equal to $k$? And if this is correct, could you present/explain a simple example of a decomposition tree that demonstrates this property?

The treewidth (and pathwidth) of the $k\times k$ grid is exactly $k$. (And, more generally, the treewidth and pathwidth of the $k\times\ell$ grid is exactly $\min\,\{k,\ell\}$). For the example grid

$$\begin{matrix}1&-&2&-&3\\|&&|&&|\\4&-&5&-&6\\|&&|&&|\\7&-&8&-&9\end{matrix}$$

the bags of the tree decomposition are $\{1,2,3,4\}, \{2,3,4,5\}, \{3,4,5,6\}, ..., \{6,7,8,9\}$.

Note that the bag $\{1,2,3,4\}$ already contains all edges adjacent to $1$, so we don't need to include that vertex ever again. Similarly, $\{2,3,4,5\}$ contains all of the edges adjacent to $2$ that weren't already in the first bag.


What is the evidence that P could equal NP? What is the evidence that P could equal NP?

I guess this is the same as asking:

If it's known that $P \subseteq NP$ (depending on standard), then why is this not enough? Why assume that P could equal NP?

This is a rather strange question to ask, given that a large majority of complexity theorists believe that P is different from NP. All the evidence we have points at P being different from NP, which is why most people believe that P doesn't equal NP.

It's like asking a climate scientist for the evidence that there is no connection between global warming and greenhouse gasses. The main difference is the standard of proof involved. The climate scientist is content with trying to convince you that there is strong evidence for anthropogenic global warming. The complexity theorist's goal is a proof, and she would not settle for less.

That said, much of complexity theory tacitly relies upon P being different from NP: if P were to equal NP, many of the results would be meaningless. Officially, such results are stated as "if P$\neq$NP then X" (such results are known as conditional results). However, the perceived semantics is simply "X holds".

Sometimes the results need a strong assumption, "if A then X", for various different As. The weaker the A, the stronger the result. Some of the assumptions A don't enjoy widespread acceptance, for example the Unique Games Conjecture. Others are considered pretty likely, such as the (Strong) Exponential Time Hypothesis. All of these are stronger assumption than P$\neq$NP (that is, they imply that P$\neq$NP).


The time complexity of the Wikipedia version of Pollards $(p-1)$ algorithm I am trying to understand the runtime of Pollard's $(p-1)$-algorithm as presented on Wikipedia. There the author writes that it takes $\mathcal{O}(B\log B\log^2n)$ time, but I do not see why.

Here the Wikipedia version:

Inputs: $n$: a composite number

Output: a nontrivial factor of $n$ or failure

select a smoothness bound $B$
define ${\displaystyle M=\prod _{{\text{primes}}~q\leq B}q^{\lfloor \log _{q}{B}\rfloor }} $ (note: explicitly evaluating $M$ may not be necessary)
randomly pick $a$ coprime to $n$ (note: we can actually fix $a$, e.g. if $n$ is odd, then we can always select $a = 2$, random selection here is not imperative)
compute $g = \operatorname{gcd}(a^M − 1, n)$ (note: exponentiation can be done modulo n)
if $1 < g < n$ then return $g$
if $g = 1$ then select a larger $B$ and go to step 2 or return failure
if $g = n$ then select a smaller $B$ and go to step 2 or return failure

I would say that:

The first step takes constant time (clear).

The second step takes $\mathcal{O}(B \log B)$ time due to the
distribution of prime numbers.

The third step takes constant time.

Concerning the 4th step: Fast-Exponentiation takes (in the version that I
know) $\mathcal{O}(\log M)$ time.   The gcd takes $\mathcal{O}(\log n)$ time. (I supposed that $ n < a^M-1$, but I am not sure if this is safe to assume.)

The remaining steps take constant time.

So because of step 2 and 4 I would say that the algorithm takes $\mathcal{O}(B \log B) + \mathcal{O}(\log n) + \mathcal{O}(\log M)$ time. What am I doing wrong?

As you mention, the costliest step is computing $a^M \bmod{n}$. This is done using the repeated squaring algorithm. Each squaring or multiplication modulo $n$ takes time $M(n)$, where $M(n)$ is the time complexity of multiplication.

We can estimate the number of multiplications by
$$
\sum_{\text{prime } q \leq B} \frac{\log B}{\log q} \cdot \log q < \pi(B) \log B = O(B).
$$
This improves slightly on the Wikipedia estimate of $O(B\log B)$.

The school multiplication algorithm takes time $O(\log^2 n)$, which is how Wikipedia got that factor. But nowadays faster algorithms are known, which run in time $\tilde{O}(\log n)$. So a better estimate on the complexity is $\tilde{O}(B\log n)$.


How to determine whether a dependent type that doesn't fit the monad instance is categorically a monad [Using Idris syntax and terminology, but the question is not about Idris]

If a monad interface (or type class) has a constraint requiring applicative functor, a monad instance can be written by implementing either bind: (>>=) : Monad m => m a -> (a -> m b) -> m b, or join : Monad m => m (m a) -> m a, or both. However, this is a much more constrained and specific type of monad than the general concept of monad in category theory.

In a dependently typed language, it is not uncommon to stick some kind of size into the type in order to allow the typechecker to recognize well-founded recursion, etc. The unfortunate impact is that because bind and join may not be size-preserving operations, you can loose your monad instance, and thus not be able to use whatever syntactic sugar the language may provide, etc. That's okay though; let's set that aside. What I'm wondering more fundamentally is if you've only lost your instance of Monad, or if your type has actually stopped being a monad. If you have a type k : Nat -> Type -> Type, might not pure : a -> k n a and (>>=) : k n a -> (a -> k m b) -> k (op n m) b / join : k n (k m a) -> k (op n m) a still satisfy the conditions to be a monad for some op : Nat -> Nat -> Nat, e.g. +?

I'll give a specific example: a freer monad indexed by size in order to allow for total operations.

||| http://okmij.org/ftp/Computation/free-monad.html
module Freer

%default total
%access public export

data FFree : (Type -> Type) -> Nat -> Type -> Type where
  FPure   : a -> FFree g n a
  FImpure : g x -> (x -> FFree g n a) -> FFree g (S n) a

Functor (FFree g n) where
  map f (FPure x)     = FPure (f x)
  map f (FImpure u q) = FImpure u (map f . q)

pure : a -> FFree g n a
pure = FPure

promote : {m : Nat} -> FFree g n a -> FFree g (n + m) a
promote (FPure x)     = FPure x
promote (FImpure u q) = FImpure u (promote . q)

assocS : (m : Nat) -> (n : Nat) -> m + S n = S (m + n)
assocS Z n = Refl
assocS (S m) n = cong $ assocS m n

apply : FFree g n (a -> b) -> FFree g m a -> FFree g (m + n) b
apply {n} {m} (FPure f) x =
  promote $ map f x
apply {n=S n} {m} (FImpure u q) x =
  let y = flip apply x . q
  in rewrite assocS m n in FImpure u y

bind : (a -> FFree g n b) -> FFree g m a -> FFree g (n + m) b
bind {n} {m} f (FPure x) = promote $ f x
bind {n} {m=S m} f (FImpure u f') =
  let y = bind f . f'
  in rewrite assocS n m in FImpure u y

join : FFree g m (FFree g n a) -> FFree g (n + m) a
join = bind id

This allow my monad methods to be total for my freer monad. But... is it still a valid monad? I do not see why adding some typelevel information would stop it from being one; other than some typelevel fanciness in the form of rewrite ... in ... etc. the method implementations are the same as those given in the "Freer Monads, More Extensible Effects" paper. However, I am used to seeing the monad laws written in terms of Monad, which I am no longer able to implement here since e.g. Free g 3 ≠ Free g 2.

How do I prove or disprove that, Monad interface and syntactic sugar aside, I still have a monad here?

So, there are potentially many answers to this sort of question. One is that there are many possible categories on which there can be monads. The rules for establishing that something is a monad will ultimately be the same, but the details will differ depending on the specific category chosen. So, since there is a natural number index involved, perhaps a monad on a category of natural number indexed types is in order, although your presentation is not precisely that. Or, perhaps you can also quantify over the natural number to get a monad that is the 'total space' of all the individual fibers. (It's also not clear to me why you need the index in this example, unless Idris has a feature that makes the type small because of it.)

However, another answer is that whether something 'is a monad' is kind of the wrong thing to worry about. Especially with examples like this, what is going on is that we are constructing the 'free algebra' of some embedded language we want to work with. Monads show up because they are one of the ways that algebra is dealt with in category theory. So because we're doing algebra, we can phrase it in terms of (a particular construction of certain) monads. But it can also be presented it in other ways as well.

The presentation you're using originates in Haskell (I think), and it's convenient there, because of impredicativity and no concern for logical consistency/termination. You can easily write down the, 'free monad over a type operator.' It's also convenient because Haskell has features that make things presented as Monad nicer to use than other presentations.

However, if Idris is not (as) accepting of definitions like that, it seems sensible to re-evaluate whether some other presentation that is accepted can encode all the things you want. For instance, there are ways of specifying strictly positive functors in more obvious ways, which give rise to e.g. W-types:

data W (A : Type) (B : A → Type) : Type where
  con : (a : A) → (y : B a → W A B) → W A B

and it's possible to construct free monads based on this:

data Free (A : Type) (B : A → Type) (X : Type) : Type where
  pure : X → Free A B X
  branch : (a : A) → (B a → Free A B X) → Free A B X

This is the free monad over the polynomial functor given by A and B (the A-fold sum of B a-fold products of X). But this is by no means the only option.

So, it seems to me that unless there is some syntax sugar or similar reason to prefer a particular solution (or you have other reasons), it's better to worry about whether you have built the algebraic structure you wanted in a way that is easy to use for whatever you actually wanted to use it for, and not whether it adheres to some particular way of doing it that works well in a different language.

And to loop around, if the size is just there for getting everything to termination check, maybe it also doesn't matter if it's any actual notion of monad from category theory. If you erased the sizes and it fit the definition of a normal monad, and the sizes are only there for book keeping, maybe that's good enough (as long as it doesn't obstruct you in more practical ways).


Is it possible to estimate the step size and walking velocity of different person with the x-y-z acceleration data from 6 axial accelerometer sensor? I have a 6-axial sensing device used to record the acceleration data. There is an algorithm used to count the number of step and walking distance of the user, but I want to further increase the accuracy of the result. I want to write an algorithm which can calculate the step size and the walking velocity of the person. Is it possible ?

The answer—as with many such applied numerical problems—is, "sure, but you have to decide which of the published heuristics you want to use". Your real problem will be the embarrassment of riches as you try to choose a paper to implement or find an existing library implementation.

Using a quick Google search on estimating step size from accelerometer, I was able to find multiple articles proposing different methods for doing this. Apparently the research area is called Pedestrian Dead Reckoning (PDR), which makes sense since dead reckoning is the general term for estimating positioning using only velocity and acceleration data.

Some articles that attempt to estimate stride length as part of a PDR algorithm include:

Ngoc-Huynh Ho, Phuc Huu Truong, and Gu-Min Jeong (2016). Step-Detection and Adaptive Step-Length Estimation for Pedestrian Dead-Reckoning at Various Walking Speeds Using a Smartphone.
Haifeng Xing et al. (2017). Pedestrian Stride Length Estimation from IMU Measurements and ANN Based Algorithm.
Ahmad Abadleh et al. (2018). Step Detection Algorithm For Accurate Distance Estimation Using Dynamic Step Length.
etc.


Insertion sort with pairs of numbers already in order I am currently attempting to work out the number of comparisons that is done by insertion sort when the elements are already in sorted pairs, for example

$$4,5,22,23,1,2,19,20, \dots$$

Currently working to solve for the worst and average case number of comparisons done when a sentinel is used.

For worst case where each pair is out of order, what I've worked out is that the pattern for comparison goes $1 + 3 + 3 + 5 + 5 ... + n + n$, leading to a summation

$$\sum_{n=2}^{n/2}(2n-1)(2)$$

and I solved it to $(n^2+4/2) - 3 - (n-2)$.

Does this look about right? I'm now having trouble attempting to solve for the average case. Any idea how to go about this? Thanks for any help

Insertion Sort is one of the algorithms which only swaps adjacent elements if they are out of order. Therefore, it's performance is intimately tied to the number of inversions in the input; see e.g. here for a detailed explanation.

Observe that in your class of inputs, the maximum number of inversions is not $n(n-1)$ as in the unrestricted case, but one less for each pair of elements. Since there are on average $\Theta(n^2)$ many inversions in random permutations, you'll have as many in your ordered-pairs permutations, assuming uniform randomness, because you lose at most linearly many in each.

For the details, find an analysis of Insertion Sort that rests on the number of inversions (e.g. in a good textbook) and change the numbers; the calculations should mostly remain the same.


Diameter-constrained Minimum Spanning Tree Problem The diameter-constrained Minimum Spanning Tree (MST) problem is as follows: you have a undirected weighted graph $G = (V,E)$ of different weights where $V$ is the set of vertices and $E$ is the set of edges between vertices, and a constant $d$. The goal is to find an MST such that the diameter (i.e., the maximum distance of the shortest paths between vertices) of the MST is at most $d$. My question is that I am debating whether the following is true or not:

  Once you have an MST of a graph $G$, if the diameter of the MST is $>d$, then is it true to say that there exist no feasible solution.

Also, once you have a MST of $G$, then is the diameter of that MST the maximum diameter of $G$? or minimum? or what could be said about the diameter of a MST?

Consider the complete graph $K_n$ in which all edges have the same cost. All trees are MSTs. They have diameter ranging from $2$ all the way to $n-1$.


Application of set theory subjects as ordinals, forcing, generic filters in software engineering I am going to teach a course in set theory for software engineering students.
I am going to talk in this course about: ordinal numbers, partial orders, well ordering, generic filters and maybe some cardinal invariants (such as $\mathfrak b$, $\mathfrak d$). I might also give a gentel introduction to forcing theory.

I was asked by the head of the department, to add to this course some application of this theory to software engineering.

Since my main area is math and not computer science, I don't have an idea for such an application.

Any ideas for such an application? If there is I would be greatfull if you could give me a detailed source.

Thank you!

Generally speaking, if you want to present some applications of the theory, it's more effective to start with applications first and teach the theory that's needed for that application, rather than select a collection of theory and then search around for some application of it.

So, one way to approach your question is to ask why the department wants software engineers to know set theory. How will set theory help software engineers?  Then once you know the answer to that question, you could devise a curriculum based upon the elements of set theory that will be relevant to software engineers.  Most likely the set of topics that should be taught to software engineers is quite different from the set of topics that we would teach to mathematicians.

If you've followed this approach to course design, you should able to answer very clearly what the applications are and why you are teaching them this material.  This approach can also potentially lead to better student engagement, depending on student's motivations.  However, this approach likely requires re-thinking the entire course and starting over from scratch on the syllabus and topics you plan to teach, which might or might not be attractive in this case.


String edit distance between strings x, y, with restrictions on 'intermediary' strings This is a problem I encountered in a recent interview test. I achieved a slow-ish solution to it, and I'm keen to figure out the most efficient.

Problem

Given a starting string $x$, a target string $y$, and a set of valid strings $V$, find the minimum edit distance between $x$ and $z$ where edits can only be character exchanges and each intermediary string $z_i$ must be in $V$.

Further constraints on problem

All strings are length 8
The complete character set for strings is $\{A, T, G, C\}$
The starting string $x$ does not need to be in $V$, but $y$ is

My Straightforward an slow-ish solution

When I see an edit-distance problem I immediately think of Dynamic Programming, but tradition Dynamic Programming approaches don't care about the intermediary stages of the string when transitioning between $x$ and $y$, so I wasn't 100% confident in this approach.

Noticing that given a small enough set $V$ I could quite quickly find all strings in it that were $1$ edit distance from my current string, I went we the following approach.

Start at string $x$ with target $y$ and set $V$ and current distance $0$

If $x == y$ the return current distance

Mark $x$ as 'seen' by removing it from $V$
Find all strings in $V$ that are 1 edit-distance from current string
recur on all candidate strings, keeping the same target, the updated $V$, and an incremented current distance

This approach isn't too terrible, and with some memoization thrown in it gets even more acceptable, but I get the strong feeling there is a much faster approach to solving the problem with out 'searching' through the set $V$.

I think your approach has merit, but you want to limit the amount of searches on $V$.

Model $V$ as a graph and connect all nodes whose strings have Hamming distance one. Then you connect $x$ and $y$ with all nodes at Hamming distance one, respectively.

Now the problem is just finding a shortest path from $x$ to $y$.


Why is the Kth Largest Element solution using a MinHeap O(N lgK) in complexity? This is a rather well known solution to the $k$-th order statistic problem which requires us to find the $k$-th largest number in an unsorted array with $n$ elements where $1 \leq k \leq n$:
public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<Integer>();

        for (int num: nums) {
            heap.add(num);

            if (heap.size() > k) {
                heap.remove();
            }
        }

        return heap.remove();
    }

A brief summary of this approach is that we maintain a min heap and keep polling from this heap each time its size exceeds $k$. This way, our final heap will contain $k$ elements, and these $k$ elements are guaranteed to be last $k$ elements in the sorted array  (since we have been polling minimums). Within these last $k$ elements, the minimum element is guaranteed to be the $k$-th largest so we extract the min and return that as a result.
What I don't particularly understand is why this problem is $\mathcal{O}(n \lg{(k)})$. For instance, after $\mathcal{O}(n)$ creation of the heap, we do an extraction of the minimum $n - k $ times, which would require sifting up in the heap $n - k$ times and hence, shouldn't this solution be $\mathcal{O}(n \lg{(n - k)})$?
Thanks!

The maximum number of elements in the heap at any given time is upper bounded by $k+1$.
Since each insertion or deletion from an heap requires $O(\log \eta)$ time where $\eta$ is the number of elements in the heap at the time of the operation, and $\eta \le k+1$, we know that each heap operation can be performed in time $O(\log (k+1) ) = O( \log k )$.
How many heap operations does the algorithm perform? Each element is inserted once, so there are $n$ insertions. In addition all but the largest $k-1$ elements are extracted. This yields a total of $n + (n-(k-1)) = 2n-k+1 = O(n)$ operations.
By multiplying the number of operations with our upper bound on the time required by each operation of $O(\log k)$  we obtain an overall time complexity of $O(n \log k)$.


Why not use the channel capacity as the sliding window size? In a sliding window protocol, if we use the maximum possible capacity of the channel as the size of the sliding window, efficiency will be theoretically 100%.
What is the logic behind not doing this?

My guess is that this is done for throttling. Are there any other reasons?

EDIT: After reading the answer by bakuriu, I come to the conclusion that using the capacity as the sliding window size can make the system unreliable:

The receiver buffer may fill up and the increased transfer rate at the sender side will become useless.
Congestion and packet loss may increase.
Reasons are pointed out in the linked answer.

But what if it is an Ethernet (preferably a LAN) using the Selective Repeat protocol for the data flow and CSMA/CD for choosing the sending station.

The receiver window would be of the same size as the sender window. So, filling up the receiver buffer should not be a concern.
There wouldn't be multiple stations competing for data transfer once the transfer has started (because of how CSMA/CD is defined).
In a wired connection (and preferably being a LAN), packet loss would be less.
Sender doesn't have to resend the whole window in case of packet loss or corrupted packet (because of Selective Repeat).

Do we usually try to use the channel capacity as the sliding window size in such (highly customized) cases?

Sliding windows are used to:

Keep track which packets were sent and received, hence the data transmission is reliable
Keep track of the memory available to the receiver. The receiver may fill its buffers and tell to the sender to slow down (because more packets will simply be dropped, causing the sender to re-send them with a probably bigger delay)

When multiple data streams pass through the same link you wont be able to use 100% of the capacity anyway, and probably more packets will be lost. In this situation sending more data simply means having to re-send the data later. That's why you want to avoid congestion and throttle the speed.

In summary: it is not true that sending data at the possible speed you can will result in the data being correctly transferred in a smaller time. It often simply means that you have to resend the same packets over again because they continue to get lost/dropped by congestioned routers/dropped by congestioned receiver. Sliding window are a way to control this and provide better overall performance.

Note: if you do not want a reliable transmission then sending at the maximum speed is better. However the amount of data that arrives correctly at the receiver may get quite small compared to what was sent.


An infinite language with no infinite RE or co-RE subsets? Are there any languages that are infinite (that is, they contain infinitely many strings) but which do not have any infinite subsets that are RE or co-RE languages? This seems related to simple sets, but I can't seem to find any examples of languages with these properties.

Thanks!

Let's prove a more general result using diagonalization. Suppose $L_1, L_2, \ldots$ is a countably infinite list of infinite languages. Then there is an infinite language $L$ that doesn't contain any of them.

We construct $L$ in infinitely many steps. At each step $t$, we keep a list of words $A_t$ in the language, and a list of words $B_t$ outside the language; these will be monotone increasing, that is, $A_t \subseteq A_{t+1}$ and $B_t \subseteq B_{t+1}$. The lists $A_t,B_t$ will always be finite and disjoint, and furthermore $|A_t|$ will grow without bounds. We can take $L$ to be the union of all $A_t$.

Let $A_{-1}=B_{-1} =\emptyset$.
At step $t$, let $B_t = B_{t-1} \cup \{x\}$ for some $x \in L_t \setminus A_{t-1}$, and $A_t = A_{t-1} \cup \{y\}$ for some $y \notin B_t$. Now $|A_t| = |B_t| = t$.

Step $t$ ensures that $L$ doesn't contain $L_t$, and at the same time that $|L| \geq t$. Taking $t\to\infty$, we deduce that $L$ is infinite and is not a superset of any $L_t$.


Why does merging two sorted arrays take 2N - 1 comparisons? A friend of mine asked me a question on how to prove that merging two sorted arrays requires at least 2N - 1 comparisons

  Prove that merging two sorted arrays of N items requires at least 2N-1 comparisons.

 /*
 * An example program that merges two arrays to prove that merging two
 * sorted arrays takes 2N - 1 comparisons.
 */
public class MergeComparisons
{
    private int comparisonCounter;
    public MergeComparisons(){
        this.comparisonCounter = 0;
    }
    public int[] merge(int[] a, int[] b) // MERGE TWO ARRAYS
    {
        int[] arr = new int[a.length + b.length];
        int i = 0, j = 0, k = 0;
        while (i < a.length && j < b.length)
        {
            comparisonCounter++;
            if (a[i] < b[j])
                arr[k++] = a[i++];
            else
                arr[k++] = b[j++];
        }
        while (i < a.length)
            arr[k++] = a[i++];
        while (j < b.length)
            arr[k++] = b[j++];
        return arr;
    }
    public int getComparisons(){
        return comparisonCounter;
    }
    public static void main(String[] args){
        int[] a = {1, 2, 3, 4, 5};
        int[] b = {6, 7, 8, 9, 10};
        MergeComparisons ms = new MergeComparisons();
        //N = 10 because we have 10 elements.
        //Comparisons should be 19.
        int[] merged = ms.merge(a, b);
        System.out.println("After merging two arrays: ");
        for(int i=0; i<merged.length; i++){
            System.out.print(merged[i] + " ");
        }
        System.out.println("\nUsed " + ms.getComparisons() + " comparisons");
    }
}

I wrote the code above to try and test the statement but it does not show. Here is the output

  After merging two arrays:  1 2 3 4 5 6 7 8 9 10  Used 5 comparisons

I was assuming it should be at least 9 comparisons from the way the question was posed.

The question asks to show the lower bound on the number of comparisons in merging two sorted arrays of length $N$. Therefore, you need to argue that no matter what comparison-based algorithm you use, it has to make $2N-1$ comparisons, otherwise it would make an error on some input, i.e., it's a worst-case analysis. An algorithm that you come up with might as well do fewer comparisons on some inputs, you just need to show it can't make fewer comparisons on all inputs.

Since we are counting comparisons, I assume we are in a so-called comparison model. Assume your arrays are $A_1 < A_2 < \ldots < A_N$ and $B_1 <  B_2 < \ldots < B_N$. Usually proofs in this model are information-theoretic. Imagine your algorithm as a comparison tree, where each node queries $A_i < B_j$ for some indices $i, j \in [N]$. Then each leaf has to correspond to a correct interleaving of the two arrays $A$ and $B$. How many interleavings are possible? Well you need to choose positions for elements of $A$ and fill in the rest with elements of $B$ (elements of $A$ and $B$ have to appear in order, so there is only one way of doing so). This leads to $2N \choose N$ possible interleavings - these should all appear as leaves in your comparison tree. If a tree has $K$ leaves it has depth at least $\log_2 K$ (since it's binary). Unfortunately, using Stirling's approximation it leads to a lower bound of $2N - \frac{1}{2} \log N - 1$, which does not match the upper bound of $2N-1$. This is surprising, because for sorting, the information-theoretic bound is optimal in the comparison model.

Knuth describes an adversarial argument (which he in turn attributes to Graham and Karp) in The Art of Computer Programming, Volume 3. It goes like this. Consider answering a query $A_i < B_j$ as "YES" when $i < j$ and "NO" as $i \ge j$. Then the algorithm will terminate at a leaf
$$ B_1 < A_1 < B_2 < A_2 < \cdots < B_N < A_N.$$
Moreover, the algorithm has to make all $2N-1$ comparisons $B_1$ vs $A_1$, $A_1$ vs $B_2$, $B_2$ vs $A_2$, and so on. Why? Suppose it doesn't perform all these comparisons. For instance it does not compare $A_1$ with $B_2$, then the following order is also consistent with our responses:
$$ B_1 < B_2 < A_1 < A_2 < B_3 < \cdots < B_N < A_N.$$


How to reduce 3-COLOR to 42-COLOR? The requirement is that two adjacent vertices have different colors, and max. 42 colors.

I show that $ \text{42-COLOR} $ is in NP and then I must reduce it from $ \text{3-COLOR} $. Here it becomes complicated.

Is it similar to $ k\text{-COLOR} $ for any $k$?

For an instance of 3-COLOR, try to add a complete graph of size $k-3$, and add an edge between each new vertex and each old vertex. Now you can prove the new graph is $k$-colorable iff the old graph is 3-colorable.


relational algebra to get unique pairs Let's say we are given this table of the relation Person(name, hobby)

name   hobby
bob    hockey
alice  basketball
mary   cricket
mark   basketball
rick   snowboarding
andy   hockey

How would I use relational algebra to find the hobby that had only one person had.

It should give me

hobby
cricket
snowboarding

My ATTEMPT:

$R1 := \rho_{P2}(Person)$

$R2 := R1 \bowtie_{P2.hobby = P1.hobby \text{ } AND \text{ } P2.name <> P1.name} R2$

$R3 := \pi_{hobby} (R2)$

You need more carefully defined $\theta$-join and then set difference:

$$R1 := \rho_{name1/name,hobby1/hobby}(Person)$$
$$R2 := Person \bowtie_{(hobby=hobby1) \land (name \neq name1)} R1$$
$$R3 := \pi_{hobby}(Person) \setminus \pi_{hobby}(R2)$$


How to avoid cascading resizes when resizing hash tables? With conventional collision resolution methods like separate chaining and linear/quadratic probing, the probe sequence for a key can be arbitrarily long - it is simply kept short with high probability by keeping the load factor of the table low. Collisions during rehashing thus aren't a problem as they don't affect the load factor.

However, with cuckoo hashing (and other methods offering worst-case O(1) lookup time?), a resize must happen when the probe sequence for a key gets too long. But when the keys get shuffled around during the rehash, it may be that they create a too-long probe sequence for one key, necessitating another resize - possibly several, if this happens multiple times in a row. The probability is small, especially with a good hash function, but I've seen it happen.

Is there a way - short of explicitly generating a perfect hash function during the rehash - to ensure that resizes can't cascade in this manner? Possibly specific to a given collision resolution scheme? The literature I've encountered thus far seems to gloss over the matter entirely. Bear in mind that I'm also interested in shrinking hash tables, not just growing them.

You ask how to avoid cascading rehashes but you already gave the answer in your post. You keep the probability that bad events occur small.

Since you mention cuckoo hashing. The probability that you get a long probing sequence is $O(1/n^2)$. So if you rehash, you are inserting $n$ elements from scratch. The probability that the rehash is not successful is then $O(1/n)$, so with very high probability you are successful. In expectation you need only a constant number of tries. If you observe that you have problems with rehashing, then you should increase your table size and modify your load factor. Alternatively you can select a better family of hash functions.


Cover interval with minimum sum intervals - DP recursion depth problem READ ME FIRST:
I have just found the official solutions online (have been looking for them for a while, but after posting this I quickly found it), and I'm currently trying to understand it. As I can tell, it uses a much simpler DP, which only uses an O(N) array.
EDIT 2
I kinda figured out what and how it does, but I still do not understand why it gives the correct answer. It uses a dp[index] -> weight sum if we select that interval and previous ones to cover [A, start_of_current].
It sorts the intervals by end time, than process each one in order. If it's start is A, we 'select' it and set it's dp[i] to it's weight. If not, it tries to find the previous selected interval whose end is closest to the current intervals start, but there is no gap in between. If found one, we 'select' the current and set it's dp[i]=it's weight + dp[j] where j is the found previous interval. If we can not find any previous, dp[i] = inf. We keep a list of the 'selected' intervals, which is, as we only push items to it, is sorted by the interval's end. When we selected one, we delete all the others from the end of this list whose cost (dp[i]) is bigger than the current one's.
What I do not get from this, is why this searching-the-closest-end yields the smallest overall weight sum, and also, why we delete all those intervals from the selection list?

Story:
This year I attended a programming competition, where we had a few interesting problems. I had trouble with some of them, and since the next round approaches, I want to clear them up.

The problem in a nutshell
We are given N weighted intervals, and a [A,B] interval. We have to cover the [A,B] interval with the given ones, in such a way, that we minimize the overall weight sum (and then the number of required intervals). We need to print the sum, the number of intervals, and then the intervals themselves. If we can not cover [A, B], we need to report that as a special value (-1).

First thoughts
If we sort the intervals by begin time, then we can do simple 0-1 Knapsack-like DP and solve the problem. Also, if the priorities were swapped (minimize count THAN sum), a simple greedy would do it.

The limits
Basically, all interval starts and ends are in the range 1-1 000 000, and N<=100 000. All intervals lie within [A,B].

My approach
I wrote a recursive algorithm like the 0-1 Knapsack one in python, that also stored the last selected interval - thus allowing the recovering of the selection list from the DP array later. It was a (current_interval, last_covered_day) -> (cost, last_selected_interval, last_covered_day')-like function. I used a dict as a DP array, as a regular array that big would have violated memory constraints and filling it fully would also increase runtime (at least that's what I thought - but a 1000000 * 100000 array would certainly would!). I wrote the function as a recursive one so it would not fill in the entire DP array and be faster & more memory-efficient.

The problem with this
Simply, I got RecursionError: maximum recursion depth exceededs on larger datasets - 100k deep recursion was simply too much. I read since on GeeksForGeeks that it should be possible to increase it, but I am still not confident that it would be safe. My recursive function is also not tail-call optimizatiable, so that would also not work.

So my questions
Is there a way of solving this problem without DP?
If no, is filling in a full table an option with those high limits?
Maybe we can come up with a different DP approach that does not use such big tables?
Is it safe to just increase recursion depth limits with this kinds of problems?

You can always convert any recursive algorithm (that uses the call stack) into a iterative algorithm where you explicitly push and pop onto a stack that you manage.  This should eliminate recursion depth exceeded errors.


How many shortest distances change when adding an edge to a graph? Let $G=(V,E)$ be some complete, weighted, undirected graph. We construct a second graph $G'=(V, E')$ by adding edges one by one from $E$ to $E'$. We add $\Theta(|V|)$ edges to $G'$ in total.

Every time we add one edge $(u,v)$ to $E'$, we consider the shortest distances between all pairs in $(V, E')$ and $(V, E' \cup \{ (u,v) \})$. We count how many of these shortest distances have changed as a consequence of adding $(u,v)$. Let $C_i$ be the number of shortest distances that change when we add the $i$th edge, and let $n$ be the number of edges we add in total.

  How big is $C = \frac{\sum_i C_i}{n}$?

As $C_i = O(|V|^2)=O(n^2)$, $C=O(n^2)$ as well. Can this bound be improved? Note that I define $C$ to be the average over all edges that were added, so a single round in which a lot of distances change is not that interesting, though it proves that $C = \Omega(n)$.

I have an algorithm for computing a geometric t-spanner greedily that works in $O(C n \log n)$ time, so if $C$ is $o(n^2)$, my algorithm is faster than the original greedy algorithm, and if $C$ is really small, potentially faster than the best known algorithm (though I doubt that).

Some problem-specific properties that might help with a good bound: the edge $(u,v)$ that is added always has larger weight than any edge already in the graph (not necessarily strictly larger). Furthermore, its weight is shorter than the shortest path between $u$ and $v$.

You may assume that the vertices correspond to points in a 2d plane and the distances between vertices are the Euclidian distances between these points. That is, every vertex $v$ corresponds to some point $(x,y)$ in the plane, and for an edge $(u,v)=((x_1,y_1),(x_2,y_2))$ its weight is equal to $\sqrt{(x_2-x_1)^2 + (y_2-y_1)^2.}$

Consider the following linear chain with $n+1$ nodes, $n$ edges and viciously chosen weights:

[source]

Clearly, the edges could have been added in order of their weights and there are $n \in \mathcal{O}(|V|)$ of them. Adding the dashed edge (which is legal) creates shorter paths for all pairs $(u_i,b_j)$ with $i,j = 1,\dots,k$. As $k \approx \frac{n}{4}$ and assuming that $n \in \Theta(|V|)$, both first and last row contain $\Theta(|V|)$ many nodes each and the addition causes $\Theta(|V|^2)$ many shortest path changes.

We can now move "outwards" now, i.e. add the next edge with weight $n+2$ between $u_{k-1}$ and $b_{k-1}$ and so on; if we continue this to $(u_1,b_1)$, we cause in total $\Theta(|V|^3)$ shortest path changes.

If this does not convince you, note that you can actually start this "process" with $(c_1,c_2)$ and work outwards from there; this way you add $\approx n$ edges which cause in total $\approx \sum_{i=1}^{n}i^2 \in \Theta(n^3) = \Theta(|V|^3)$ many shortest path changes---this is just impossible to draw to fit on one screen.


Computational Complexity of Promise Monotone 1 in 3 SAT Given a 3SAT problem where each clause is a Monotone Clause (i.e. each clause with all positive or negative literals).

Moreover, we are promised that each solution for the above SAT problem (if any exists at all) will be of the form 1 in 3 SAT.

Monotone 1 in 3 SAT is NP Complete, but with the additional promise above, does the problem still remain NP Complete (it obviously is NP) ?

The trivial answer is no, as promise problems cannot be (by definition) in NP, and thus cannot be NP complete. The basic complexity classes e.g. $P, NP$ refer only to decision problems.

However, if you want to relate your promise problem to the standard classes, you can say it is NP-hard in the sense that if it can be solved in polynomial time for inputs in the promise, then $P=NP$.

To see why the above holds, let us introduce some notations. Let $C$ be the set of all monotone clause 3CNF, for which all satisfying assignments are 1 in 3. We shall call this set "the promise". Now your problem is, given an input in $C$, to determine whether it lies in $L_{yes}=C\cap SAT$, or in $L_{no}=C\setminus L_{yes}=C\cap\overline{SAT}$.
Given an instance $\varphi$ to monotone clause 1 in 3 SAT, transform it to a monotone clause 3CNF $\psi$ such that $\psi\in C$, and in addition every 1 in 3 satisfying assignment for $\varphi$ also satisfies $\psi$. You can construct $\psi$ by adding clauses which negate conjunctions of pairs of literals in the same clause. Since $\psi\in C$ for every possible $\varphi$, and in addition $\varphi$ has a one in three satisfying assignment iff $\psi\in L_{yes}$, then solving the promise problem in polynomial time allows you to determine whether $\varphi$ has a one in three satisfying assignment, and thus $P=NP$.

The above basically shows that you can reduce an NP complete problem to your promise problem, but when talking about promise problems the definition of reduction should be slightly adjusted. Let us say that $f$ is a reduction from $L$ to the promise problem $L_{yes}\cup L_{no}$ if $Im(f)\subseteq L_{yes}\cup L_{no}$ and for every $x$ it holds that $x\in L\iff f(x)\in L_{yes}$. This is equivalent to saying that  $x\in L\Rightarrow f(x)\in L_{yes}$ and $x\notin L\Rightarrow f(x)\in L_{no}$ (note that not being in $L_{yes}$ does not imply being in $L_{no}$).


Looking for memory-efficient way to detect hash collisions Given a hash function H, it's possible that H(a) = H(b) = c

Let's assume we have a big data set [N1 ... Nk], with K items and we hash each item in this set

After operation is done, we'd get a set of hashes [H1 ... Hm] where m < k, meaning we had collisions

What would be the most memory-efficient way(without storing all of hashes and hashed items) to determine if we've ever hashed item X before and if we did, did it collide with anything?

Is it even possible to relax memory constrains on such kind of task?

Assume you have a good hash function producing an n bit hash code, that is $2^n$ possible values. Assume you are hashing k values, so there are about $k^2/2$ pairs of hash codes that might collide. The probability of a collision is about $k^2 / 2^{n+1}$.
By picking a large n, you can make that probability arbitrarily small. Ask a physicist to calculate the probability that your computer will be hit by a meteor and completely destroyed, together with all hash values. Pick n large enough that the probability of a collission is say 1,000 times smaller than the probability of a total destruction of the computer involved.
You might also consider what is the amount of damage if you have a collission. For example, the damage could be that as a result, there will be one person in the world who can enter your country with the passport of one specific other person. Make n large enough so that the expect damage through a collision is negligible.
(That's the principle behind the use of GUIDs. There is no guarantee that there are no collisions, but with a proper implementation the probability can be neglected. )


Can literals in functional languages be thought of as functions from the empty type? A while ago, I think on Stack Overflow, I saw someone say that Haskell literals can be thought of as functions that don't operate on anything. This makes sense to me but I remember someone else vehemently disagreeing with him.

If I understand correctly, all values in primitive types, or at least those in Bool, are type constructors, and type constructors are a special kind of function into the type. Since values like 2.87, True, or 'f' don't have any parameters passed to them it seems like it wouldn't effect the semantics of the language whether you think of them just as elements of their type or a functions from a type containing nothing into their type that always returns their value. Is there anything wrong with thinking of literals in this way?

Let's start in a total language like Agda.  Then, as gallais states, this only makes sense if by "empty type" you mean the unit type, i.e. the 0-ary tuple, which has exactly one value. The empty type can be thought of as a 0-case sum type, and has no values at all. In Agda, you can easily prove that Unit -> A is isomorphic to A. In that sense, you can consider them the same, though they still aren't literally the same. I can't, for example, do a case analysis on a Unit -> Bool nor can I apply True : Bool to anything as a function.

The story for Haskell is quite different. () -> A and A are semantically non-isomorphic types. In particular, () -> () has four values, while () has only 2. The four observationally distinct values are undefined, \_ -> undefined, \x -> x, \_ -> (). So () isn't actually a unit type, in the sense that there is exactly one function into (). (In Agda, on the other hand, we can prove that if x : Unit and y : Unit, then they are equal [definitionally so if we define Unit with the record syntax as opposed to the data syntax]. That means, Unit has only one value. Further, we can prove that Unit and A -> Unit are isomorphic for any A.)

In fact, an "empty" type like Void defined as data Void is closer to being a unit type in this sense. Void has only one value, but Void -> Void still has two. In fact, every function type A -> B, has at least two observationally distinct values, namely undefined and \_ -> undefined. Therefore, Haskell has no true unit or void type.

A lot of this is due to Haskell being a non-strict language and is exasperated by the existence of seq (and its equivalents). For example, the distinction between undefined and \_ -> undefined can only be seen with seq. If we eliminated seq and its equivalents from Haskell, then Void would serve as a unit type, though, ironically, still not as an empty type.

Usually, when people talk about such things in Haskell, they are tacitly pretending that Haskell is a better behaved language than it is. That is, they are assuming bottoms don't exist for their purposes, i.e. that you're working in a total language like Agda. For the purposes of designing your code, this is usually adequate; it's not common that we care about or expect bottoms. These distinctions can become important if we're doing something like circular programming, or if safety guarantees of our program rely on these properties, e.g. a function can never be called if it has an empty type as its domain.


Languages of cardinality higher than $\aleph_0$ I was studying model theory and that's how I came across formal languages. I looked around but it seems as though a language (set of strings over some alphabet) is usually treated as being finite or countable. Just wondering if languages of higher cardinality have been investigated. Any references would be nice.

Thank you!

EDIT: I found an answer. Infinitary logic deals with just such a question. See here. It allows formulas of infinite length, so the collection of all such formulas could be uncountable. I guess in the CS world a formula is simply a legally formed word (based on some rules). The set of all such legal formulas could be uncountable.

I'm choosing to leave this question here as it might help another beginner like myself.

EDIT 2: Another way maths allows uncountable languages is to allow uncountably many symbols in the signature (which would be a subset of alphabet in the CS world). So even if formulas (i.e. words) can only be finitely long, there can be uncountably many of them.

I've realized the question isn't so much about formal languages as it is about logic. It was due to my ignorance that I posted the question here. My humble apologies!

In traditional Formal Language theory, all languages are countable. This is because they're defined as a subset of $\Sigma^*$, so they always contain strings of finite length, meaning we can map them to integers.

We rarely deal with finite languages, since all finite languages are regular, and therefore trivially decidable.

There has been research into the computability of functions on real numbers. The difficulty here is that in practice, there's no single way to represent arbitrary real numbers. A common method is looking at, given a real-valued function $f$, inputs $\vec{x} $ and an integer $n$,
can we use a Turing Machine to compute a representation $f(\vec{x})$ to $n$ digits of precision?

You could view a real number as justing being a function taking $0$ arguments, so a real number $r$ is can be seen as a function from $n$ to the first $n$ binary digits of $r$.

Interestingly, since Turing Machines are finite, the set of all Turing Machines is countable, so the set of all computable real numbers is countable, meaning there are many more uncomputable reals than computable ones.

For more info, see http://en.wikipedia.org/wiki/Computable_number.

Note that there's also a concept of automata on infinite words, used in formal language theory and program verification. These languages can be uncountable: an infinite sequence of $0$s and $1$s is equivalent to a subset of $\mathbb{N}$ so an automaton that accepts all such words accepts an uncountable language.


Why is it most efficient to resize a dynamic array to 2 * array.length()? By dynamic array, I mean an array that when it becomes full we replace it with a new array having greater capacity than the previous array.

I read in a textbook that doubling the size of the array is the most efficient resizing. I want to know if this is in fact demonstrably true and not just a matter of personal preference.

We will want to minimize the amount of resizing events, because each such event requires O(n) time where n is the number of elements in the list.

We also should be careful not to make the list too big because it might be a waste of memory.

Why does the author of my textbook say that 2 * array.length() is the magic number?

Consider a model in which elements are only added, one at a time, and once an array is full, it is increased in size by a factor of $C$. Suppose also that resizing an array of size $x$ costs $Cx$. Adding $N = C^n$ elements (the worst case in terms of resizing cost per element) has cost $C(1+C+C^2+\cdots+C^n) \approx \frac{C^2}{C-1} N$. The amortized cost of adding an element is thus $f(C) = \frac{C^2}{C-1}$. The derivative of this function is
$$
f'(C) = \frac{2C(C-1)-C^2}{(C-1)^2} = \frac{C(2-C)}{(C-1)^2},
$$
which vanishes at $C=2$. It is not hard to check that this is a minimum of $f(C)$.


Route finding on a graph that must go through multiple edges I have this graph

It shows a graph of a map that has nodes and segments (or edges), with weights, that connect these nodes. Some of these segments have addresses on, and some of these addresses are designated as restaurants. There are two chosen restaurants, and one chosen address.
Can someone point me in the direction of an algorithm that would calculate the best path to get from any segment, through each of the segments containing the chosen restaurants, and ending at the chosen address?
So far I have looked at Christofides Algorithm, and Dijkstra's Algorithm, neither of which seem to solve this problem, or atleast i cannot work out how to alter the algorithms to make them work for this problem.

I have decided that the best solution to this is a variation on Dijkstra's algorithm. Since it doesn't require a Hamiltonian Circuit and makes it easy to manage the weights. I will also use Homeomorphism as suggested in the comments of the question to make weighting the distance between the nodes and addresses more accurate.


Prove EXPTIME \ NP is not a subset of NP-Hard? If we assume that NP is not equal to co-NP, how do we show that EXPTIME \ NP is not a subset of NP-Hard?

Hint: note co-NP $\subseteq$ EXPTIME, and co-NP-complete $\cap$ NP = $\emptyset$ since NP $\neq$ co-NP, it remains to prove co-NP-complete $\nsubseteq$ NP-hard.

   Further hint: if co-NP-complete $\subseteq$ NP-hard, try to show for each language $L\in$ NP, you can build a NTM deciding $\bar L$, thus NP $\subseteq$ co-NP, a contradiction.


Number of binary trees with given height I was wondering how many binary trees we have with height of $h$ with $n$ nodes(another question is how many binary trees we have with height $ \lfloor{lg (n)}\rfloor$).

Edit: I forgot to add the number of nodes.

I assume that a binary tree is given by the following specification: a binary tree is either (a) empty or (b) is composed of a root and two (ordered) subtrees.

I also assume that height is defined so that a complete binary tree of height $h$ has $2^{h+1}-1$ nodes (for example, a single node has height $0$).

Let $A_h$ be the number of binary trees with height at most $h$. Then $A_{-1} = 1$ and $A_h = 1 + A_{h-1}^2$. This is A003095. The number of trees with height exactly $h$ is $A_h - A_{h-1}$, which is A001699. Both sequences have asymptotics of the form $\alpha^{2^h}$ for some $\alpha > 1$.


Why this Turing machine can't be an acceptor for the following language? Given the following language -
$L=\left\{\left\langle M_{1}, M_{2}\right\rangle \mid\left\langle M_{1}\right\rangle \notin L\left(M_{2}\right) \vee\left\langle M_{2}\right\rangle \notin L\left(M_{1}\right) \text { and are TM } M_{1}, M_{2}\right\}$
I know it's in CO-RE but why this is not a good acceptor for the above language?
On input $<M1,M2>$

In parallel simulate M1 on $<M2>$ and M2 on $<M1>$
if one rejects, accept.
if both accept , reject.

according to definition of being acceptor of a language, for any input x that belongs to the language the acceptor accepts which it does it at phase 1. for any input which doesn't belongs to the language we either reject or not halt which is also the case.
what am i missing?

You are not considering the fact that $M_1(M_2)$ and/or $M_2(M_1)$ might not halt. When this happens your Turing machine for $L$ will be stuck executing step 1.


Which algorithm for predicting the next word(s) based on previous words, given a sentence? I want to input some words, and out comes the next word(s). Neural nets are really hot at the moment, and I'm afraid of throwing a neural net at something, when one is not really needed. Or... maybe it is needed?

My current options are:

Predict next word(s) using N-grams
Predict next word(s) using a neural net

There are quite a number of Github repositories that does this using neural nets, and a few that does it with N-grams. Are there any clear advantages to choosing the neural net approach?

You can use anything you like.  Right now neural networks are the state of the art: they produce the best predictions.  But you could also use HMMs, or n-grams, or other methods; they just will be lower quality than a state-of-the-art neural network.


Solve recurrence T(n)=2T(n-1)+n for n greater than 1 and T(1)=1 Problem statement: Solve $T(n)$ for $T(n)=2T(n-1)+n$, $n > 1$, and  $T(1)=1$.

My attempt: I tried back substituting but I am unable to find a general pattern:
$$\begin{align*}
T(n) &=2^2 T(n-2)+3n-2 \\
&=2^3 T(n-3)+7n-10 \\
&=2^4 T(n-4)+15n-34 \\
&=\cdots
\end{align*}$$

Hint:
$$\begin{align*}
T(n) &= 2T(n-1) + n \\
&= 2^2 T(n-2) + (2n + n) - 2 \\
&= 2^3 T(n-3) + (2^2n + 2n + n) - (2^2 \cdot 2 - 2) \\
&= 2^4 T(n-4) + (2^3n + 2^2n + 2n + n) - (2^3 \cdot 3 + 2^2 \cdot 2 + 2^1 \cdot 1) \\
&= \cdots
\end{align*}$$

If you are familiar with the required methods, you can also solve it using generating functions (and, e.g., techniques from here or chapter 7 of "Concrete Mathematics" by Graham, Knuth, et al.).


In instructions pipelining, why does register read/write take up only half clock cycle? While studying instruction pipelining in MIPS processor, we make an assumption that registers read/write stages take only a half clock cycle, as this picture shows (half clock cycles are dotted in register operations):

So what is the purpose of this assumption? and why is the fourth instruction in this graph is considered a hazard if we actually wrote the value of $2 in the first half clock cycle and then read it in the latter one?

By using different phases of a clock cycle for register write and register read, the number of register file ports can be reduced. (This can reduce area and latency.) A two-read and one-write instruction would otherwise require three register file ports (or introduce a structural hazard); by using different phases of the cycle one port can be used for both read and write. This can also facilitate reading from the register file in the same cycle as the value is written, which reduces the number of results that must be managed through the forwarding network.

The fourth instruction (add $14, $2, $2) does not have a data hazard even without forwarding.


Are all non-terminals of the CFG given by the LHS of productions? A definition for terminals and non-terminals of a CFG says that

  terminals: The symbols that do not appear at the LHS of productions.

Therefore,

Are all non-terminals of the CFG given by the LHS of productions?

No. Not all non-terminals necessarily appear at the LHS of productions, that is, not every non-terminal must have productions for it.

Of course, such non-terminals are rather useless and can be removed from the grammar without changing the language. Also the dual is actually possible: there might be terminal symbols that do not appear at the RHS of productions. For example $a^*$ is a context-free language over the alphabet $\{a,b\}$.


Looking for a use case of a $k$-$d$ tree with a norm other than $L^2$ In Python's implementation of $k$-$d$ tree
it is possible to manually change the norm used for computing distances from
$L^2$ to $L^p$.

When would one use a norm other than $L^2$ in a $k$-$d$ tree?

For example, when you want to report all the points in distance $r$ from a query point under the $L_1$ norm, which is a natural case. See https://en.wikipedia.org/wiki/Taxicab_geometry.


A Query regarding Quadratic Residuocity Problem In number theory, an integer q is called a quadratic residue modulo n if it is congruent to a perfect square modulo n; i.e., if there exists an integer x such that:
$$
    x^2\equiv q \pmod{n}.
$$Otherwise, q is called a quadratic nonresidue modulo n.

Problem Definition: Given a constant c, is there a positive integer x < c such that
$$
    x^2\equiv q \pmod{n}.
$$

If n is composite, the problem is NP-Complete, even if given the prime factorization of n. But, if n is a prime the problem is solvable in polynomial time.

Query: In case n is composite, and given that it has lets say exactly 3 distinct prime factors, does the problem still remain NP-Complete? Any link to the references?

It can be solved in randomized polynomial time, so it's not NP-complete (unless RP=NP, which is considered unlikely).

If $n=p_1p_2p_3$ is composite, where $p_1,p_2,p_3$ are three distinct prime factors, and $p_1,p_2,p_3$ are given, then the problem can be solved in polynomial time.  In particular, in this case, there are only 8 square roots of $q$ (modulo $n$), and you can enumerate them all and check whether any of them are in the range $[0,c)$.

Details and justification: you can use the Chinese remainder theorem.  Let $x_1$ be one of the two square roots of $q$ modulo $p_1$, i.e., it satisfies $x_1^2 \equiv q \pmod{p_1}$.  (Then the other square root is $-x_1$.)  Similarly, let $x_2$ be a square root modulo $p_2$ and $x_3$ a square root modulo $p_3$.  Then you can find a square root modulo $n$ by using the Chinese remainder theorem to find the unique solution to $x \equiv x_1 \pmod{p_1}$, $x \equiv x_2 \pmod{p_2}$, $x \equiv x_3 \pmod{p_3}$.  In general, you can look for $x$ to be $x_1$ or $-x_1$ mod $p_1$, and $x_2$ or $-x_2$ mod $p_2$, and $x_3$ or $-x_3$ mod $p_3$; each of those $2 \times 2 \times 2 = 8$ combinations gives a different square root of $q$ modulo $n$.  You can find $x_1,x_2,x_3$ in randomized polynomial time, and the CRT computation can be done in polynomial time, so you can enumerate all square roots modulo $n$ in polynomial time.

This same argument generalizes to any case where the number of prime factors of $n$ is constant, and where those prime factors are given in advance.  However, when the number of prime factors is unlimited, this line of argument doesn't work, so this won't work for general $n$.