How to get expected running time of hash table?

If you think of $1000$ as a constant, then yes, the running time is terrible. The idea of hash tables is that if the hash table is moderately bigger than the amount of data stored in it, then operations are very fast. Suppose for example that the hash table has size $m = 2n$. Then each operation takes constant time in expectation.

In implementations of hash tables, the hash table expands as more entries are inserted, to ensure that the ratio $\alpha$ is reasonable. Amortized analysis shows that this does not cause a performance hit in terms of the total running time, though individual operations might be slower (this is only a problem if you're writing a real-time application).


Do we generally store the degree of each vertex in the linked list implementation? if not, why?

Normally we don't; the adjacency list representation is a list of out-edges, but doesn't separately store the degree.  However, you can certainly store that additional information if you want.  You can choose how you want to represent the graph, and it's not hard to modify the standard data structure to keep track of the out-degree of each vertex.


If all you require is a polynomial-time reduction, then test in polynomial time if $G$ is $2$-colourable. If it is, map it to the formula $X$; if it isn't, map it to $X\land\lnot X$.


Infinite non-regular decompositions of regular languages

Your intuition does not match mine, I think this is possible for every initial (infinite) regular language. My idea is that every infinite language has an (infinite) non-regular subset, such that the complement is also infinite. You then can repeatedly find the next language which together form a non-regular decomposition.

How to prove the basic observation? Just set half of the words apart (for the complement, the set of words is countable, so order them). In the remaining words you choose a subset that has ever greater sizes, not growing linearly but at least say exponential. Such a subset cannot be regular.

How do we obtain a decomposition that way: we might omit a string in each step. This is dealt by taking the shortest remaining string in the next language. That choice does not influence any regularity.


This is an educated guess of the transliterated names I could find in the Paxos paper. Most of these are people mentioned in the paper's references.

Λ˘ινχ∂: Lynch, N. - Legislator
Φισ∂ερ: Fischer, M. J. - Legislator
Tωυεγ: Toueg, S. - Legislator
Ωκι: Oki, B. M. - Legislator
∆ωλεφ: Dolev, D. - Farmer
Σκεεν: Skeen, M. D. - Merchant
Στωκµε˘ιρ: Stockmeyer, L. - Legislator
Στρωνγ: (Strong/Strang?) - Legislator
∆φωρκ: Dwork, C. - President
∆˘ικστρα: Dijkstra, E. W. - Cheese inspector
Γωυδα: (Gouda) - Cheese inspector
Φρανσεζ: Francez, N. - Wine taster
Πνυeλ˘ι: Pnueli, A. - Wine taster
Σ∂ν˘ιδερ: Schneider, F. B. - Citizen
Γρεες: (Greece) - Citizen
Λαµπσων: Lampson, B. - General
Λισκωφ: Liskov, B. H. - Merchant
Παρνας: Parnas, D. - Elder statesman
Γρα˘ι: Gray, C. G. - Priest
Λινσε˘ι: Lindsey, B. G. - Priest


Take $A=NP$, as you requested.  $P^{NP}$ is not necessarily equal to $NP$.

Let me give an example why not.  Consider TAUTOLOGY (given a boolean formula $\varphi$, is it true for all possible assignments to the variables?).  TAUTOLOGY is known to be co-NP-complete.  Therefore, TAUTOLOGY most likely is not in NP, since if TAUTOLOGY were in NP, it would follow that NP = co-NP, which is widely suspected not to be the case.

However, TAUTOLOGY is certainly in $P^{NP}$.  Here's why.  Given an oracle for SAT, we can solve TAUTOLOGY as follows: query whether $\varphi$ is in SAT; then flip the answer (if $\varphi$ is in SAT, answer "no, $\varphi$ is not in TAUTOLOGY"; if $\varphi$ is not in SAT, answer "yes, $\varphi$ is in TAUTOLOGY").  This shows how to solve TAUTOLOGY in polynomial time given an oracle for SAT, and SAT is in NP, so this shows that TAUTOLOGY is in $P^{NP}$.

So TAUTOLOGY is an example of a problem that is in $P^{NP}$, but probably isn't in NP (unless NP = co-NP).  Hopefully this helps illustrate why NP is not the same as $P^{NP}$.

If not, here's a little more intuition.  NP is a particular class.  $P^{NP}$ is the class of problems that can be solved by querying an oracle for NP, possibly many times.   The "many times" part is the key difference between NP and $P^{NP}$.  A (many-one) reduction between two NP problems can only query a NP-oracle once, while $P^{NP}$ allows you to query the oracle as many times as you like.  That seems to be a lot more powerful,  and it's the reason why $P^{NP}$ seems to be a bigger class than NP.


How to create a model which predicts the radius of a circle?

Finding reasonably-regular shapes in noisy data? I'd try classical techniques first, like RANSAC or a Hough transform.

Why machine learning?


Maximum Capacity Path Problem with constraints

It can be solved in polynomial time. For instance, you can use binary search over the weight.  Given a candidate weight, delete all edges with lower weight, then find the lowest-cost path and test whether its cost is below the lower bound; that tells you whether the weight was too high or too low.  Repeat until binary search converges.


When converted to 0s and 1s, they're not words anymore, they are a configuration for the machine. In a way, they are words only as a help to our human understanding. As it often happens, we end up confusing our own conceptions with reality.

Computer networks, distributed systems and interactive computing add other layers of complexity to this picture. Since you cannot consider standalone computer as closed systems of hardware and software, it becomes even more tempting to see programs as transcendent writings, whose meaning commands the machines were they run.

It is definitely not the case. Words are aids, nothing more.

To put it differently: a program, or any kind of source code, is already given to the compiler as a sequence of 0s and 1s. Even if not directly composed of machine instructions, this sequence of bits can be deterministically converted to machine code. That's what a program translator (compiler, interpreter, emulator, etc.) does.


Suppose $A$ and $B$ are regular. Let $M_A$ and $M_B$ be DFAs for $A$ and $B$, respectively. We know $M_A$ and $M_B$ exists since every regular language is accepted by some $DFA$.

Let $M_A = (\Sigma, Q, q_0, A, \delta)$ and $M_B = (\Sigma', Q', q_0', A', \delta')$.

We define $M_C = (\Sigma'', Q'', q_0'', A'', \delta'')$ such that $L(M_C) = shuffle(A,B)$.

First, let $\Sigma'' = \Sigma \cup \Sigma'$.

Next, choose $Q'' = \{0, 1\} \times Q \times Q'$.

Now, choose $A'' = \{(0, q, q') \mid q \in A, q' \in A' \}$.

Let $q_0'' = (0, q_0, q_0')$.

Now the fun part: what is the transition function? Here's what it's going to do:

If $q'' = (0, q, q')$, then $\delta''(\sigma, q'') = (1, \delta(\sigma, q), q')$ if $\delta(\sigma, q)$ is defined, or undefined otherwise (we're going to get an NFA, but that's OK).
If $q'' = (1, q, q')$, then $\delta''(\sigma, q'') = (0, q, \delta'(\sigma, q'))$ if $\delta'(\sigma, q')$ is defined, or undefined otherwise (again, we're going to get an NFA, but that's good enough for establishing regularity).

Basically, we're using the state to encode whether the last symbol we saw was from a word in $A$ or from a word in $B$. We can only accept if the last symbol we saw was from a word in $B$, hence our set of accepting states requiring that we have 0 for the parity. Furthermore, we can only accept if we've seen a complete word from both $A$ and $B$, which is why we require the other components to be accepting states in their respective automata.

You can think of this as two simultaneous DFAs produced from the Cartesian-Product construction for the intersection of the languages. After evaluating each step, we jump to the other machine. The first machine accepts input corresponding to the language $A$, and the second machine accepts input corresponding to the language $B$.

The full proof that this construction yields a correct automaton is left as an exercise.

Note that this construction technically allows $k = 0$, which is not allowed by the language in the question. To complete the exercise, argue that the NFA obtained above can be converted to a DFA by a standard construction, and that intersecting the resulting DFA with a DFA for the language of positive-length strings gives a DFA for the desired language.


How to find how many times an object's path crosses another?

This can be done by what I'd call "accelerated replay" (I'm making up this term).

Let's suppose the movement of each object is piecewise linear: each object moves in a straight line at a constant speed for a while, then changes direction and moves in a different direction at a different speed, etc.  So, object $i$'s path can be specified a sequence of times $t_{i,0},t_{i,1},\dots,t_{i,n}$ at which the object changes direction; between times $t_{i,j}$ to $t_{i,j+1}$, the object is moving in a straight line (with known endpoints) at a constant speed.  The algorithm can be generalized to allow each individual piece of the path to be curved or other shapes as well, but it's easiest to describe in this setting.

So, let's take the union of all of the times $t_{i,j}$ and sort them.  In this way, we get a set of "events", where each "event" corresponds to an object changing direction/speed.  Now, we're going to replay all of the object movements.  However, we're going to "fast forward" through all of the times that fall between two adjacent events.  In other words, we're going to iterate through the events in time order.

At a single step of the algorithm, we're going to be processing a particular event, say the event at time $t_{i,j}$ where object $i$ changes direction.  We know the line segment that each of the other objects are currently on; and we know the line segment that object $i$ will travel on after time $t_{i,j}$.  So, for each other object $i'$, compute the location where the lines for objects $i$ and $i'$ intersect, check the time when that will happen, and check whether that time is before the end time for both line segments; if so, you've found a cross-over.  Notice that finding the intersection point of two line segments can be done in constant time ($O(1)$ time).  Once you've done that, you've taken into account all cross-overs that can occur until the next event.  So, no need to continue simulating what happens in any future time, until the next event.  So, fast-forward to the next event, and then do the same thing for the next event.

The total running time will be $O(nm)$, where $n$ is the number of objects and $m$ is the total number of events.  Or, if you expect $q$ events per object (i.e., $q$ changes of direction), then the total running time will be $O(n^2q)$.  Since you have only a few hundred objects, that should be quite reasonable.

It's plausible to me that it might be possible to reduce this to something more like $O(nq \log n)$, using techniques from computational geometry (e.g., Shamos-Hoey etc.), if that were really necessary -- but I haven't tried to think about whether that's possible, as given the numbers you listed in your question, the algorithm above should be fine.

If you want to find "points of closest approach" instead of "crossovers", it's easy to adjust the above algorithm to do that.  Given two line segments, it is easy to find their point of closest approach in $O(1)$ time, so then you just apply the same ideas as before.  If you want to deal with curved trajectories, that is also possible; if you have two curved lines that are parts of a circle, it is also possible to find whether they intersect in $O(1)$ time using some trigonometry, so again you can generalize the above algorithm to handle that as well.

There are probably many pragmatic ways one could speed this up, e.g., by using quadtrees to separate the plane into multiple regions and map each part of the path to the region(s) it visits, and then only look for crossovers within each region.


Orderability of Belief States in a POMDP?

Having recently worked on this topic, I can say that the answer to both of your questions is yes.

The belief states may be partially ordered for example applying the monotone likelihood ratio, or other appropriate stochastic orderings that tell when a probability mass function (pmf) $f$ -- here a belief state -- is "greater than" another pmf $g$.

Roughly speaking, if the POMDP state transition and observation models are such that the partial order is preserved on a belief update operation, structural statements about the optimal policy of the POMDP can be made. Details may be found in a recent journal paper: V. Krishnamurthy, U. Pareek, Myopic Bounds for Optimal Policies of POMDPs: An extension of Lovejoy’s Structural Results, Operations Research, 2014; available at the author's website. The article also provides a literature review on the topic where further references may be found.

Krishnamurthy and collaborators also have a paper where the MLR ordering is applied on a single line in the belief space, on which the MLR order applies to every belief state: V. Krishnamurthy, D. Djonin, Structured Threshold Policies for Dynamic Sensor Scheduling--A POMDP Approach, IEEE Trans Signal Processing, Vol.55, No.10, pp.4938--4957.


How to sort an array $A[1..i..n]$ where $A[i] \in \{1,2,..,n^5 \}$ in $\Theta (n)$ time?

Radix sort for integers of arbitrary length has $\mathcal{O}(mn)$ time complexity, where m is the length of number.
Count digits takes $\mathcal{O}(\log(n))$ time, so, your cycle will take at least (in worst case though) $\mathcal{O}(n \log(n))$ time which is the best possible for general case of sorting problem. Because to find complexity of 2-level cycle, you need to find complexity of subcycle and multiply them.

Of course, there exists an algorithm that can sort any array of numbers in $\mathcal{O}(n \log(n))$ time and $O(\log(n))$ space.


Why is $L := \{b^2a^nb^ma^3|m,n \geq 0\}$ a regular language?

The pumping lemma says that there is some $p$ such that every string longer than $p$ can be split in some way that can be pumped.

You've shown that there's some $p$ and some splitting that doesn't work but (since the language is regular), that just means you chose the wrong $p$ and/or the wrong splitting of your string.

In fact, the value of $p$ is the number of states in the smallest automaton that accepts the language (plus one, I think). The language you give is going to need about eight or nine states, so your $p$ was too small. However, that doesn't much matter. Given the string $b^2a^{p-3}ba^3$, we can split it as $x=b^2$, $y=a$, $z= [\text{the rest}]$ and now $xy^iz\in L$ for all $i\geq 0$, as the pumping lemma claims.  Sure, some other splits don't work, but that one does and the lemma just claims that some split works.

Remember: to show that a language is non-regular using the pumping lemma, you need to show that, for every $p$, there is at least one word of length at least $p$ in the language such that every valid splitting as $xyz$ results in $xy^iz\notin L$ for at least one $i$.


Abs(sum of differences of elements in a sorted array) = array.Max()-array.Min() Why?

If you picture these as distances along a road, it should be very intuitive.

If (for example) you start at kilometer #7, then proceed through kilometers #45, #81, and #97, then the distances you travel are 45−7, then 81−45, then 97−81; and the total distance you travel is 97−7. Since the total distance is the sum of the individual distances, 97−7 = (45−7) + (81−45) + (97−81).

This only works for a sorted set, because otherwise you have backtracking, where you cover a certain distance and then "un-cover".


What is the "formula" for "any cipher can be deciphered by a quantum computer"?

In general, if NP turns out to be the subset of any tractable class then that will be a black swan event for those who depend on cryptography as it exists today.  $NP \subseteq BQP$ is one such example. But it need not be a fatal blow to use of cryptography.  Quantum computers with a large number of qubits have yet to be built, and it is unknown whether they can be.  So increasing key lengths may well put tractable decryption out of reach of the machines that can be built.  And of course the polynomial exponent might turn out to be large enough to make polynomial-time "efficient" decryption infeasible in practice.  E.g. an $O(n^{13})$ algorithm for SAT, while a beautiful thing to behold, probably isn't going to break use of cryptography.


Does a multi cpu system not improve the first come first serve (fcfs) cpu scheduling algorithm?

Sounds like something's very wrong.  My guess is that you are testing with a load that is too small.  You should be able to increase the number of processes and at some point the 4-processor system should be able to handle about 4 times as many processes.

Let's try a simple asymptotic analysis:

Suppose we have $N$ processes each of which goes through the following cycle repeatedly (forever):

Wait in the ready queue until a CPU is available.
Run on the CPU for average time $S$.
Request an I/O that takes average time $Z$.
Go back to the ready queue.

What's the minimum average response time $R_{\mathrm{min}}$, for going through this cycle once?   $S+Z$.  (That's the average time for service at the CPU plus average time for I/O, and no time waiting in the queue.)  So

$$ R \geq S+Z.  $$

Now Little's Law says that the average response time $R$ is equal to the number of processes in the system, $N$, divided by the system throughput, $X$ (in units of number of times through the entire cycle each second).

$$ R = \frac{N}{X}. $$

What's the maximum throughput this system can achieve.  That would happen in the (unrealistic) case that all the processors were busy all the time.  There are $P$ processors and each CPU burst consumes average time $S$, so the maximum throughput is $P/S$.  That is $X \leq P/S$.  So

$$ R \geq \frac{N}{X} = \frac{NS}{P}. $$

That is, when $\frac{NS}{P} \geq S+Z$ you should start to see the average response time increasing linearly as you increase the number of jobs in the system.  Below that and you won't see much difference.


It looks like you are trying to compute a hypergraph transversal of size $k$. That is, $\{T_1,\dots,T_m\}$ is your hypergraph, and $S$ is your transversal. A standard translation is to express the clauses as you have, and then translate the length restriction into a cardinality constraint.

So use your existing encoding, i.e., $\bigwedge_{1 \le j \le m} \bigvee_{i \in T_j} x_i$ and then add clauses encoding $\sum_{1 \le i \le n} x_i \le k$.

$\sum_{1 \le i \le n} x_i \le k$ is a cardinality constraint. There are various different cardinality constraint translations into SAT.

The simplest but rather large cardinality constraint translation is just $\bigwedge_{X \subseteq \{1,\dots,n\}, |X| = k+1} \bigvee_{i \in X} \neg x_i$. In this way each disjunction represents the constraint $\neg \bigwedge_{i \in X} x_i$ - for all subsets $X$ of $\{1,\dots,n\}$ of size k+1. That is, we ensure that there is no way that more than k variables can be set. Note that this is not polynomial size in $k$

Some links to papers on more space-efficient cardinality constraint translations which are polynomial size in $k$:

Translating Pseudo-Boolean Constraints into SAT - Niklas Eén and Niklas Sörensson, JSAT vol 2 (2006), pg 1-26 (a good survey).
Efficient CNF encoding of Boolean cardinality constraints - Olivier Bailleux and Yacine Boufkhad, Proceedings of Principles and Practice of Constraint Programming 2003, LNCS vol 2833, pg 108-122 (a nice, fairly easy to implement translation).
Towards an Optimal CNF Encoding of Boolean Cardinality Constraints - Carsten Sinz - Proceedings of Principles and Practice of Constraint Programming 2005, LNCS 3709, pg 827-831.
Towards Robust CNF Encodings of Cardinality Constraints - Joao Marques-Silva and Inês Lynce, Proceedings of Principles and Practice of Constraint Programming 2007, LNCS 4741, pg 483-497.

If you are actually interested in solving such problems, perhaps it is better to formulate them as pseudo-boolean problems (see wiki article on pseudo-boolean problems) and use pseudo-boolean solvers (see pseudo-boolean competition). That way the cardinality constraints are just pseudo-boolean constraints and are part of the language - hopefully the pseudo-boolean solver then handles them directly and therefore more efficiently.


Fast, stable, almost in-place radix and merge sorts

Here is description of the proposed algorithm.

The algorithm is further improvement of the one proposed in Parallel radix sort with virtual memory and write-combining. They implemented fastest parallel LSD radix sort that avoids the counting pass by using "indefinite" space for output buckets. Each bucket allocs space on-demand using hardware paged memory support. A comprehensive study of main-memory partitioning and its application to large-scale comparison- and radix-sort took this idea further, proposing software implementation of the paged memory, that allows to perform stable radix/merge/quick sort using only $O(\sqrt{NR})$ extra memory.

Basic operations of radix, merge and quick sort have something in common:

radix sort pass: read from 1 stream and write into R streams
merge: read from R streams and write into 1 stream
partition: read from 1 stream and write into R streams

Each of these operations process its input and output streams in strictly sequential manner. On every step, input plus output streams contain exactly N elements total - we neither produce nor consume any data items, but only move them between streams. This allows to implement in-place list-processing versions of these algorithms that don't move any data at all and only modify next list pointers. And this brings us to idea that we can perform these operations on array in-place, allocating only a little more space to perform home-made memory management of the array space.

To accomplish that, we split input and output streams into fixed-size pages and maintain list of pages in the each stream. When an input stream consumed all data on a page - this page is moved into the freepage list. When output stream needs more space - it allocs a page from the freepage list. Each stream may have incomplete first and last page, so in the worst case we may have 2*R*PAGESIZE unused items at any given moment - it's the extra space we need to alloc in addition to the page management structures. It's easy to find that the optimal PAGESIZE is $O(\sqrt{N/R})$ and the entire extra memory usage is $O(\sqrt{NR})$.

A few concrete examples:

2-way sorting of 1 million 8-byte items, i.e. 8 MB: we need 4 extra pages and can fit page number into 16 bits. 2 KB pages are optimal, and we need 16 KB of extra space total.
256-way sorting of the same array: we need 512 extra pages, while page number still fits into 16 bits. 256 byte pages are optimal, and we need 192 KB of extra space total. It's 2% of 8 MB, which is the largest proportion among these examples.
2-way sorting of 128 millions 8-byte items, i.e. 1 GB: we need 4 extra pages, and page number still fits into 16 bits. 32 KB pages are optimal, and we need 192 KB of extra space total. You may note that the two later cases has the same R*N and hence the same memory requirements.
256-way sorting of the same array: we need 512 extra pages, and page number finally requires full 32 bits. 4 KB pages are optimal, and we need 3 MB of extra space total.

TL;DR: sorting more than 1 MB of data usually requires less than 10% extra space, and the proportion reduces as datasize grows.

Algorithm: utility functions

Let's define data structures for our memory manager:

// Number of items per page
const int PAGESIZE = 1024; // just for example

const int PAGE_COUNT = N/PAGESIZE;

// next_page[page] is either -1 (meaning EOF)
// or index of the next page in the same stream
int next_page[PAGE_COUNT];

// Input and output streams
StreamDescriptor in_streams[R];
StreamDescriptor out_streams[R];

struct StreamDescriptor
{
    int first_page;
    int first_element;  // index of first element on the first page
    int last_page;
    int last_element;  // index of last element on the last page + 1
    // all pages between the first and last ones are fully populated
};

Here is the "memory manager" which allows to alloc new pages for output streams and release pages consumed from input streams:

// head of the available pages LIFO queue
int first_available_page;

int AllocPage()
{
    int page = first_available_page;
    assert(page != -1);
    first_available_page = next_page[first_available_page];
    return page;
}

void ReleasePage(int page)
{
    next_page[page] = first_available_page;
    first_available_page = page;
}

// Main data storage (holding N elements) provided by the caller
T* MainArray;

// Extra memory allocated for temporary data storage
T* ExtraPages;

// Return address of given memory page
T* Page (int page)
{
    if (page < PAGE_COUNT)
        return MainArray + PAGESIZE*page;
    else
        return ExtraPages + PAGESIZE*(page - PAGE_COUNT);
}

And these operations read item from given input stream and write item into given output stream:

T get_next_item (int input_stream)
{
    StreamDescriptor s = in_streams[input_stream];
    if (s.first_page == s.last_page  &&  s.first_element == s.last_element)
    {
        ReleasePage(s.first_page);
        return EOF;
    }
    if (s.first_element == PAGESIZE)
    {
        int next = next_page[s.first_page];
        ReleasePage(s.first_page);
        if (next == -1)
            return EOF;
        s.first_page = next;
        s.first_element = 0;
    }
    return Page(s.first_page)[s.first_element++];
}

void put_item (int output_stream, T item)
{
    StreamDescriptor s = out_streams[output_stream];
    if (s.last_element == PAGESIZE)
    {
        int next = AllocPage();
        next_page[s.last_page] = next;
        s.last_page = next;
        s.last_element = 0;
    }
    Page(s.last_page)[s.last_element++] = item;
}

Algorithm: LSD radix sort

Initialization depends on the amount of input and output streams. For example, prior to first pass of LSD sort we do the following:

void LsdRadixSort (T* data_to_sort, int N)
{
    MainArray = data_to_sort;
    ExtraPages = new T[2*R*PAGESIZE];

    // Setup first input stream as containing the entire MainArray contents
    in_streams[0].first_page = 0;
    in_streams[0].first_element = 0;
    in_streams[0].last_page = PAGE_COUNT-1;
    in_streams[0].last_element = N % PAGESIZE;

    for (int i=0; i<PAGE_COUNT-1; i++)
        next_page[i] = i+1;
    next_page[PAGE_COUNT-1] = -1;

    // Alloc one initial page for each outstream
    for (int i=0; i<R; i++)
    {
        int page = PAGE_COUNT+i;
        out_streams[i].first_page = page;
        out_streams[i].first_element = 0;
        out_streams[i].last_page = page;
        out_streams[i].last_element = 0;
    }

    first_available_page = -1;

    ...
}

Prior to second and following passes of LSD sort, we perform this:

// Make old out_streams new in_streams
for (int i=0; i<R; i++)
{
    in_streams[i] = out_streams[i];
}

cur_input_stream = 0;

// Alloc one initial page for each outstream
for (int i=0; i<R; i++)
{
    int page = AllocPage();
    out_streams[i].first_page = page;
    out_streams[i].first_element = 0;
    out_streams[i].last_page = page;
    out_streams[i].last_element = 0;
}

In the first pass, data should be read with get_next_item(0) calls until it returns EOF. On the second and following passes, data should be read using the following procedure, also up to EOF:

// Enumerate contents of all input streams in order
T get_next_item_2nd()
{
    if (cur_input_stream >= R)
        return EOF;

    T item = get_next_item(cur_input_stream);
    if (item==EOF)
    {
        ++cur_input_stream;
        return get_next_item_2nd();
    }

    return item;
}

One pass of LSD radix sort:

void one_pass(int pass)
{
    for(;;)
    {
        T item  =  pass==1? get_next_item(0) : get_next_item_2nd();
        if (item==EOF)
            break;
        int bucket = calc_bucket(item,pass);
        put_item(bucket,item);
    }
}

Algorithm: reordering data

Once sorting is finished, the caller may either read data in sorted order using the same get_next_item_2nd() procedure, or data may be placed in proper order in original array.

Reordering requires two steps:

compact data into single stream, removing "holes"
move each page of the compacted stream into right place

For the first step, we can just append to the first stream contents of remaining streams:

// Make old out_streams new in_streams (except for the first one)
for (int i=1; i<R; i++)
{
    in_streams[i] = out_streams[i];
}

cur_input_stream = 1;

// Move data from all streams into the first one
for(;;)
{
    T item = get_next_item_2nd();
    if (item==EOF)
        break;
    put_item(0,item);
}

For the second step, we start with enumerating pages in the single stream remaining, and marking all other (i.e. free) pages with -1:

// final_place and next_page are the same array used in different roles
int* const final_place = next_page;

int page_i = out_streams[0].first_page;

for (int i=0; i<PAGE_COUNT; i++)
{
    int next = next_page[page_i];
    final_place[page_i] = i;
    page_i = next;
}

while (first_available_page != -1)
{
    int next = next_page[first_available_page];
    final_place[first_available_page] = -1;
    first_available_page = next;
}

From this point on, final_place[pg] is a page where current contents of page pg should be finally placed, or -1 for a page whose contents is garbage and so can be overwritten. Now all that remains is the classic "move them all to their final places" algorithm:

for (int i=0; i<PAGE_COUNT+2*R; i++)
{
    int page = i;

    while (final_place[page] != -1  &&  final_place[page] != page)
    {
        mem_exchange( Page(page), Page(final_place[page]), PAGESIZE*sizeof(T));
        std::swap( final_place[page], final_place[final_place[page]]);
    }
}


Yes, the complement of a regular language is regular.
If $L$ is regular then there is a DFA accepting that language. In particular, its states can be classified as ACCEPTING states and non-ACCEPTING states. Just turn non-ACCEPTING states into ACCEPTING, and ACCEPTING states into non-ACCEPTING states and you will have a DFA accepting $\overline{L}$.


Given language consisting Turing machines is decidable or not?

In other words, $L=\{\langle M \rangle:L(M)\notin \{\phi,\Sigma^*\}\}$. you can show explicit reduction from a language you already know is not in $RE$. for example $\overline{HP}$ (it is a very standard reduction).
or you may use the rice theorem to show that.

I did not understand the reduction you suggested.
The reduction from the language you suggested could be as follows:
$$f(\langle M \rangle,x)=\langle M_x \rangle$$

$M_x$ on input w:

run $M$ on x for |w| steps.
if $M$ accepted then reject, otherwise accept.

Note that $\epsilon \in L(M_x)$ in anycase, so $L(M_x)\neq \phi$. and $L(M_x)\neq\Sigma^{*}\iff x\in L(M)$. the correctness follows.


Which AC-3 algorithm is being used here?

The Fig. 5 in the question depicts AC-algorithm with backtracking.

In fact, without backtracking, checking arc-consistency alone can hardly solve the 4-Queen problem. Unless it happens that choices made so far will be extended to a desired configuration, any algorithm to solve CSP have to backtrack so as to check other possibilities.

Here is a relevant excerpt from the article.

  Conversely, if it does not become possible to place a Queen at  the  pointed  column,  like  in  Fig. 5(c),  backtracker  will backtrack  the  previous  assigned  Queen’s  column  to  reassign the conflicted Queen to a newly safe cell at the same column. Then, it will, at first, clear the constraints it created by calling the implemented modular function.


Why is fully homomorphic encryption so slow?

I don't know how to answer why it's slow; it's slow because it's slow? The algorithm involves a lot of computation, and that takes a long time to do.

Is it possible to make a fast FHE?  No one knows.  It's an open problem.  If it was easy, we would have done it so far.  So either it's not possible; or it's possible but it's challenging and we currently don't know how to do it.

In some sense, it's not surprising that FHE is a lot slower than traditional cryptography.  FHE imposes some very strong requirements on the encryption scheme.  This constrains what kind of encryption scheme you can use.  It's no surprise that if you add extra requirements, it's harder to make the scheme also be fast; and it feels reasonable that the stronger the requirements, the slower this might make the scheme.  In this case, the FHE requirement is very strong indeed.

I'm not aware of any proof that FHE must be slow.  However, there are some results that may be somewhat indicative.  In particular, the following paper shows that any FHE scheme can be broken in subexponential time (while we believe that traditional encryption schemes require exponential time to break).  This means that the FHE scheme will require larger parameter sizes to be secure.  Usually, larger parameter sizes mean that the scheme will be slower.  So, that is some weak indication that FHE schemes will need to be slower.  However, it doesn't really answer the question; it's just a hint.

Algorithms for black box fields and their application to cryptography.  Dan Boneh, Richard Lipton. CRYPTO '96.


How to solve variable sized bin packing when the items have equal weights, or is it still NP-hard?

I'll change the description to avoid artificial sums.

We have n bins $bin_i$. Each bin has a capacity $C_i$ and a weight $f_i$. We have m items $item_i$. Each item has a weight $w_j$. We want to pick a set B of bins, and for each $bin_i$ in B a set $I_i$ such that the weights of all items in $I_i$ is at most $C_i$, and the sum of the weights $f_i$ of the bins in B is minimised. Each item must be in exactly one of the bins $bin_i$ in B. We assume $f_i > 0$ and $w_i > 0$.

If all $w_i = w$ are the same, then we can divide each $C_i$ by w and replace $w_i$ by 1 without changing the problem. Now the number of items in $I_i$ must be ≤ $C_i$. Since the number of items in $I_i$ is an integer, we can round each $C_i$ down to the nearest integer without changing the problem.

There are m items, and each item is exactly in one bin, so the sum of the $C_i$ for bins $bin_i$ in B is ≥ m for a solution. On the other hand, if the sum of $C_i$ for bins in B is ≥ m, then we can fit the m items into those bins (because the $C_i$ are integers). So now we can completely ignore the items, and the problem is: Find a set B of bins so that the sum of $C_i$ for bins in B is ≥ m, while the sum of $f_i$ for those bins is minimised. If we find the set B, then putting items into the bins is trivial.

Let B' be the set of bins not in B, and let C be the sum of all $C_i$. Instead of finding B, we can find B' such that the sum of $C_i$ for bins in B' is ≤ C - m, and the sum of $f_i$ for bins in B' is maximised. We rename "bin" to "item" and call B' a "knapsack", and voila - a knapsack problem. Very much easier to solve than the original problem if the number of bins is significantly smaller than the number of items, but still NP-complete.


Is there a fast solution for this set reduction problem?

This rewriting system is confluent, so if you just repeatedly pick a legal transformation and apply it, over and over again, until  you can't any longer ... you will always end at the same state.

In other words, there is a unique end state from which no further transformations are possible, and you can reach it by any sequence of legal transformations.  Define a state to be a final state if no further transformations are possible from it.  Then there is a unique final state, so you can reach it by following any legal sequence of transformations and continuing until you can't continue any further.  (This will terminate, since each step reduces the size of $L$.  By definition, once you can't continue, you are in a final state.  Since the final state is unique, this terminates at the unique final state.)

You can even find the shortest such sequence, relatively efficiently.  Build an undirected graph with one vertex for each $p_i$, and with an edge $(p_i, p_j)$ if $p_i \cap p_j \ne \emptyset$.  Compute the connected components of this graph.  Then the final state will have one subset per connected component in the graph; it will be a subset containing the union of all of the vertices of the connected component.  You can get to that connected component by repeatedly picking some pair of vertices $p_i,p_j$ that are joined by an edge, merging those two vertices into a new vertex $p'$, and then updating the edges ($p'$ gets an edge to each vertex that had an edge to either $p_i$ or $p_j$; but remove all self-loops).  If there are $n$ vertices originally and $c$ connected components, this will terminate after $n-c+1$ steps.

In fact, looking at it a bit longer, you can discover that any legal sequence of valid transformations that ends at a final state is equally good -- all such sequences have the same length.  You start with $L$ containing $n$ subsets; you end with $L$ containing $c$ subsets; each transformation reduces the length of $L$ by one; so any such sequence must contain exactly $n-c+1$ steps.  All the legal sequences end at the same final state, so all sequences are equally good.

TL;DR: At each step, apply any valid transformation.  Eventually you will terminate.  It doesn't matter which pair of subsets you choose to merge at each step; you'll eventually end at the same ending point, and the total number of steps will be the same regardless of the choices you make at each step.

This is the most wonderful kind of algorithm: at each step, do anything that's not illegal, and you'll eventually end up a winner.  You can't lose!


Comparing variable image to static image

I think you're really asking for a distance metric on images.  Based on  your examples, I would suggest the L2 distance (sum of squares of differences in pixel intensities) or L1 distance; possibly after aligning the images.  This looks like it should b effective for the examples you list.


Is there a way to theoretically compare hash functions?

One measure to compare two hash function is the expected value of collision in the hash function. Now, based on the expected value, if a hash function has a lower collision in the expected sense could be a better hash function here. This expectation can be estimated by a random sample with a proper size from the specified domain.

Moreover, hash functions are compared base on their time complexity too, which is not your case here.


Spatial data structures are part of Computational Geometry?

You need spatial data structures as part of computational geometry, to have at least some reasonable base reference against which to compare the time and memory consumption of special purpose (sweepline/randomized) algorithm. For this purpose, BVH is too vaguely defined to be useful (except for summarizing a common principle for some better specified data structures), but kD-trees are good enough for this purpose.

I don't see where you would need spatial data structures for non-geometry related data structures and algorithms, so I would say it is only a part of it, if you study geometry (or GIS) related problems. But if anybody shows me a non-geometry related application, then I'm quite willing to change my mind.

For geometric modeling, things like constructive solid geometry, homogeneous coordinates, Bézier curves, B-splines and NURBS should come first, because understanding them is also important when just using existing geometry modeling software. But BVH fits in well, because it is an intuitive geometric concept. It can sometimes be useful for understanding the performance behavior of existing geometry modeling software (sometimes the user can even influence the BVH to improve performance). I see fewer reasons why kD-trees should be part of geometric modeling.


Solving constants in the recursive term with master theorem

If you are just interested in an upper bound you can notice that $T(n) \le S(n)$ where $S(n) = 3 S(n/3) + \frac{n}{2}$ and has solution $S(n) = O(n \log n)$.
Alternatively there is always induction. You can show that, for $n \ge 2$,  $T(n) \le c n \log n$.
For $2 \le n < 7$, $T(n)$ is a constant and $n \log n \ge 1$. Therefore the claim is true for a sufficiently large (constant) value $c^*$ of $c$.
For $n \ge 7$ you have:
$$
T(n) = 3T\left(\frac{n}{3} - 2\right) + \frac{n}{2} \le 3 c \frac{n}{3} \log \frac{n}{3} + \frac{n}{2}
= cn \log n - cn \log 3 + \frac{n}{2},
$$
which is at most $cn \log n$ when $c n \log 3 \ge \frac{n}{2}$ or, equivalently, $c \ge \frac{1}{2 \log 3}$.
Simply pick $c = \max\{c^*, \frac{1}{2 \log 3} \}$.


Since any input x for L can be reduced to SAT in O(|x|^c) time, the created SAT instance will have size at most n=O(|x|^c).  So the n^(lg n)-time algorithm for SAT will be an |x|^O(lg |x|)-time algorithm for L.


Decision vs Optimization version for Problems of two Parameters

Having more than one input doesn't change anything:

Consider an optimization problem $MinQ$:

  Input: $x, k$
  Output: find $y$ satisfying $Q(x,k,y)$ which minimizes $f(x,k,y)$:
  $$g(x,k) = \min_{y : Q(x,k,y)} f(x,k,y)$$

The corresponding decision problem $Q$ is:

  Input: $x, k, l$
  Query: is there a $y$ satisfying $Q(x,k,l)$ such that $f(x,k,y) \leq l$?

To solve the decision problem,
we can solve the optimization problem,
then check if the output is less than $l$.
I.e. there is a very easy reduction from $Q$ to $MinQ$:

  input: $x,k,l$
  1. $m = MinQ(x,k)$
  2. return $m \leq k$


Representation of -40 in 8bit computer using 2's complement

First of all, 40 in binary is 101000.

The 8-bit representation is obtained by zero-padding: 00101000.

The one's complement of this is obtained by inverting the bits: 11010111.

To obtain the two's complement, we simply add 1: 11011000.


What you are trying to do is find the arboricity of the graph, or equivalently compute the minimum partition into independent sets in the graphic matroid. This problem (for a general matroid) is known as the Matroid partitioning problem, for which polynomial-time algorithms exist.
You can find more details in Harold N. Gabow and Herbert H. Westermann, Forests, frames, and games: Algorithms for matroid sums and applications.


Synchronous model: is taking steps simultaneously equivalent to having fixed upper bounds for communication/processing delays?

All of these are, generally speaking, called "synchronous models", they are pretty similar to each other, and especially in the context of fault-tolerant algorithms they are very different from "asynchronous models".

However, please note that there is no such thing as the synchronous model. Even if you define a message-passing model in which all nodes execution proceeds in synchronous rounds and all nodes start simultaneously, this does not yet completely define the model of computing. To have a well-defined model of distributed computing, you will need to specify, e.g., the following aspects:

assumptions on the underlying network topology (complete network? path? cycle? grid? bounded-degree graph? arbitrary graph?)
what kind of local information the nodes have in the beginning (unique identifiers? an upper bound on the network size?)
what is the communication model (maximum message size? can you send different messages to each neighbour in the same round or are you limited to e.g. broadcast operations? can you receive messages from different neighbours in the same round or do you have collisions? how can you address your neighbours?)
what kind of computers you have as your nodes (finite state machines? Turing machines? arbitrary functions? any limitations on time or space used per round? any limitations on space used between rounds? can you use randomness?).

These aspects can be much more important than the specific definitions of "synchrony", especially if you are interested in computability.

But let us put these issues aside, let us assume we have already precisely defined some synchronous model of computing (and let us also assume that it is a fairly strong model, e.g., we have unique identifiers and unlimited local computation). Let us now try to see whether the precise definition of "synchrony" would make any difference.

If you only care about computability, the precise definition of "synchrony" is not important. Also, if you are only interested in the number of communication rounds needed to solve a problem (and you define a "communication round" appropriately so that it makes sense also in the bounded-delay model), the models are also equivalent up to constant factors. In essence, you can simply use the alpha synchroniser: all nodes count rounds from 1, all messages include round counters, and each node proceeds to round $i+1$ once it has received all messages from round $i$ (and you use timeouts to detect nodes that have crashed).

Things get more complicated if you also care about e.g. the total number of bits that you need to transmit. In essence, in the "strict" synchronous model you can easily use silence to send information (e.g., be silent for $x$ rounds and then send a 1-bit message ≈ send number $x$). Here is a simple example of a problem that can be solved this way:

the underlying graph is a path and all nodes need to determine how far they are from the nearest endpoint.

If all nodes start simultaneously and computation proceeds in synchronous rounds, it is sufficient to propagate a 1-bit token from the endpoints towards the middle. All nodes can locally count how many rounds it takes before they receive the token. In total, in a path of length $n$, you will send approximately $n$ messages, each of them containing just one bit.

However, if you have bounded delays, it gets pretty tricky to solve this problem with $O(n)$ 1-bit messages. You can still use periods of silence to send information, but you will need to waste a lot of time to do that (a naive solution has an exponential time complexity).


Firstly, you need to figure out what is the length of your input. Your input is $n$ so you need log(n) bits. Denote this number as $m$ not to get confused. Division takes either linear of m or constant time, depending on your model. So the question is how many time you gonna run it. Clearly, sqrt(n) times where $n=2^m$ so this algorithm runs in $O(2^{\frac{m}{2}})$ time.


HOG vs. neural networks for person detection

Unfortunately, this remains a very challenging problem, that even state-of-the-art techniques find difficult to do accurately.  It's probably too hard for a high school project.

The closest work is probably on "pedestrian detection".  Do a search on Google Scholar, and you should find a bunch of research papers on this from the computer vision community.  However, the state-of-the-art techniques are complex, and even the best techniques aren't super accurate.

You should also read about "object detection", "object recognition", and related topics.  That will give you the basics of how to use machine learning (like neural networks) to recognize the location of objects in an image.  One standard technique is to crop out a small rectangle from the image, use your classifier to check it contains the object you're looking for (e.g., a person), and then repeat this for many crops of many different regions of the image -- this tells you the location of all people.  There are other approaches as well, based on regression to infer the location of the object.

You might find Stanford's CS231N useful for learning more about these techniques.

For your specific problem, doing this in the general case is probably too hard.  I'd advise you to look for a way to make the problem easier.  One way is to make the problem more constrained and place your cameras carefully to make the machine learning problem easier.

For instance, if the room is a lecture hall where everyone will be seated and facing the same direction, you could experiment with placing a camera that will see everyone from the front, and using facial detection to identify and count the number of faces in the image.  Or, you could place a video camera at each entrance and exit and use facial detection or other methods to try to recognize people when they are entering/leaving the room, and count the number who have entered and the number who have left.  This will probably be easier if you have two video cameras over each door: one on the outside pointing in, and one on the inside pointing out.  Or, you could experiment with entirely different sensors, such as a FLIR camera which can see in the infrared.  People are warm and glow in the FLIR wavelengths, which might make it easier to distinguish people from other elements of the scene.


A basic result in elementary arithmetic states that
$$
\log_a n = \log_a b \cdot \log_b n.
$$
Indeed, on the one hand, $a^{\log_a n}$ by definition. On the other hand,
$$
a^{\log_a b \cdot \log_b n} = (a^{\log_a b})^{\log_b n} = b^{\log_b n} = n.
$$
Similarly,
$$
\log_b n = \log_b a \cdot \log_a n.
$$
This shows that every two logarithms only differ by a constant multiple. Since big O notation discounts constant factors, it doesn't matter which logarithm you use (unless it's in the exponent). For example, a function is $O(\log_a n)$ iff it is $O(\log_b n)$. For this reason we usually don't bother writing the basis of a logarithm in big O notation.


If a predicate is not computable, what can be said about its negation?

If a function F is computable, so is !F, as you can simply compute F and return the negated result.

For the same reason, if a function isn't computable, neither is its negation.


Prove function in little-oh of a big-theta function

$f(n)$ is $o( g(n) )$

This above equation implies the following:

$f(n) < c \cdot g(n) \  -(1)$

for some $c \in R$ and $\forall n \geq n_{0}$

$g(n)$ is $\Theta( h(n) )$

The above equation implies following:

$ c_{1} \cdot h(n) \leq g(n) \leq c_{2} \cdot h(n) -(2)$

for some $c1, c2 \in R$ and $\forall n \geq n_{0}'$

Now let's assume $c$ > 0

Multiplying equation $(2)$ by $c$ gives:

$ c \cdot c_{1} \cdot h(n) \leq c \cdot g(n) \leq c \cdot c_{2} \cdot h(n)$

Considering right side of the above inequality:

$c \cdot g(n) \leq c \cdot c_{2} \cdot h(n)  -(3)$

Let $n_{0}''$ be $max(n_{0}, n_{0}')$

We can say $\forall n \geq n_{0}''$, equation $(1)$, $(2)$ and $(3)$ will hold true. Now by using $(1)$ and $(3)$, we can infer:

$ c \cdot c_{2} \cdot h(n) > f(n) -(4)$

Let $c' = c \cdot c_{2}$

Therefore we can write equation $(4)$ as:

$ f(n) < c' \cdot h(n)$

$\forall n \geq n_{0}''$ and since $R$ is closed under multiplication, therefore $c \in R$

which implies $f(n)$ is $o(h(n))$.

Note: For $c < 0$, you can consider left side of the inequality, which after multiplying by $c$ will actually come to right side (since $c < 0$).


Proving a language to be Recursively Enumerable?

Your language is computable, and so in particular recursively enumerable. Given a path on the Cartesian plane, you can decide whether it goes back where it started: just follow the path and see where it ends. You can program a computer to do that. So it is decidable.


Conflict Driven Clause Learning combined with brute force

Your reasoning is valid, but it won't help a SAT solver go much faster.  Your method produces long clauses that only forbid a single assignment.  What you want to speed up a recursively searching SAT solver is to learn short clauses that forbid many assignments.  That requires a more sophisticated learning strategy than adding a simple disjunction of the negation of the current variable assignment.


Maximum number of vertices in undirected graph

Kruskal's algorithm is only applied to connected graphs. These have at least $|V|-1$ edges. On the other hand, the complete graph has $\binom{|V|}{2}$ edges, and so
$$
|V|-1 \leq |E| \leq \binom{|V|}{2}.
$$
The left-hand side is $\Omega(|V|)$ and the right-hand side is $O(|V|^2)$. Therefore $\log |E| = \Theta(\log |V|)$. For this reason, the two quoted running times $O(|E| \log |E|)$ and $O(|E| \log |V|)$ are completely identical — on connected graphs, an algorithm has running time $O(|E| \log |E|)$ iff it has running time $O(|E| \log |V|)$.


There is a second solution to the conundrum, which is Quine's NF (New Foundations) set theory.

NF is a set theory that avoid the paradox, but a set of all sets does exist. NF avoids Russell's paradox by putting constraints on the what formulae are allowed in comprehension. In other words the predicate $\phi$ in

$$
   \{x\ |\ \phi(x)\}
$$

does not range over all predicates, but only over predicates that are "well-stratified". In particular, $true$ is well-stratified, so the universe

$$
   U = \{x\ |\ true\}
$$

is a set in NF. A first-order logic formula $\phi$ in the language of set-theory (i.e. $\in$ is the sole non-equality predicate) is well-stratified, provided there is a function

$$level : Vars \rightarrow \mathbb{N}$$

(Here $Vars$ is the set of all variables) such that the following holds.

For all sub-formulae $x \in y$ in $\phi$: $level(x) + 1 = level(y)$.
For all sub-formulae $x = y$ in $\phi$: $level(x)  = level(y)$.

In summary, while ZF(C) set-theory avoids Russell's paradox by prohibiting sets that are too big, NF avoids Russell's paradox by prohibiting sets that are too ugly.


Relational query for universally quantified formula

SQL does not have a universal quantifier, but an equivalent can be constructed from the existential one, through a normalization process similar to Skolemization: $$\forall x P(x) \iff \nexists x \neg P(x)$$

In your case, you want the users for which there does not exist a book that they have not borrowed:

select * from people p
where not exists
  (select * from books b
   where b.id not in
     (select book_id
      from borrowings
      where people_id=p.id)
  )

(Note that I have assumed tables for people and books to represent their existence separately from the borrowings table, which, for instance, may be empty at the inception of the system.)


Any word can be written as a concatenation of runs. For example,
$$ aaabbabaccbbbc = a^3b^2a^1b^1a^1c^2b^3c^1. $$
Each run is a positive power of a symbol, and the constraint is that two adjacent runs are powers of different symbols. Each word can be decomposed into runs in a unique way.
The regular expression $(a+b)^*c^*(a+b)^*$ captures all words with at most one $c$-run. Similarly, the regular expression $(b+c)^*a^*(b+c)^*$ captures all words with at most one $a$-run. Therefore the intersection consists of all words with at most one $c$-run and at most one $a$-run.
Since the only other possible run is a $b$-run, we get that the intersection is
$$
b^*a^*b^*c^*b^* + b^*c^*b^*a^*b^*.
$$


Let me call $
\mathcal{X}_1 = \{x \in \mathcal{Z}^n: w^{\top}x \leq b \}
$
and
$
\mathcal{X}_2 = \{x \in \mathcal{Z}^n: \lfloor w\rfloor ^{\top}x \leq \lfloor b\rfloor \}
$ to avoid confusion.

Let $x \in \mathcal{X}_1$. Then: $$b \ge w^T x = \sum_{i : x_i = 1} w_i$$ which implies:
 $$\lfloor b \rfloor \ge  \left\lfloor  \sum_{i : x_i = 1} w_i \right\rfloor \ge \sum_{i : x_i = 1} \lfloor w_i \rfloor = \lfloor w \rfloor^T x.$$

Therefore $x \in \mathcal{X}_2$, and this shows that $\mathcal{X}_1 \subseteq \mathcal{X}_2$.


What is a recursion for Huffman encoding?

Huffman's algorithm uses the greedy heuristic, which is different from the dynamic programming approach in the other problem you mention. However, we can still define the cost recursively.

There are actually several options. In all cases, given a distribution $p_1,\ldots,p_n$, we will find a formula for $C(p_1,\ldots,p_n)$, which is the optimal cost of a prefix code.

Let's start with Huffman's algorithm itself:

$C(1) = 0$.
$C(p_1,\ldots,p_n) = p_i + p_j + C(p_1,\ldots,\widehat{p_i},\ldots,\widehat{p_j},\ldots,p_n,p_i+p_j)$, where $p_i,p_j$ (for $i < j$) are the two smallest probabilities (i.e. $\max(p_i,p_j) \leq p_k$ for all $k \neq i,j$), and $\widehat{p_i}$ signifies that $p_i$ is removed.

The proof that this recurrence is correct is not immediate.

If we want a Huffman-like recurrence whose correctness is immediate, we need to tweak this only slightly:

$C(1) = 0$.
$C(p_1,\ldots,p_n) = \min_{i<j} [p_i + p_j + C(p_1,\ldots,\widehat{p_i},\ldots,\widehat{p_j},\ldots,p_n,p_i+p_j)]$.

This recurrence holds since (i) given a code for $p_1,\ldots,\widehat{p_i},\ldots,\widehat{p_j},\ldots,p_n,p_i+p_j$ we can get a code for $p_1,\ldots,p_n$ which is worse by $p_i+p_j$ by splitting the node corresponding to $p_i+p_j$ into two, and (ii) given a code for $p_1,\ldots,p_n$, if we choose any two sibling leaves $p_i,p_j$ then $C(p_1,\ldots,p_n) = p_i + p_j + C(p_1,\ldots,\widehat{p_i},\ldots,\widehat{p_j},\ldots,p_n,p_i+p_j)$.

A short reflection reveals that we can always ensure $j = n$ (say), and this leads to a simpler recurrence:

$C(1) = 0$.
$C(p_1,\ldots,p_n) = \min_{i<n} [p_i + p_n + C(p_1,\ldots,\widehat{p_i},\ldots,p_{n-1},p_i+p_n)]$.

The last two recurrences are bottom-up. There is also a top-down recurrence:

$C(1) = 0$.
$C(p_1,\ldots,p_n) = 1 + \min_{S \sqcup T = [n]} [C(p_S) + C(p_T)]$, where the minimization is over all partitions of $\{1,\ldots,n\}$ into two non-empty sets, and $p_S = (p_i : i \in S)$.

In this recurrence we are splitting the root instead of merging two sibling leaves. I leave to correctness proof for the reader.

Only the first recurrence above can be implemented efficiently.


Which of the following regular expressions generate(s) no string with two consecutive 1’s?

III is $(0+1)^* (0+ \epsilon)$ which means pick a word from $\Sigma^*$ where $\Sigma = \{0, 1 \}$ and then concatenate it with either $0$ or $\epsilon$.

so III Does generate a string with two consecutive $1$'s. In fact it generates every string which contains $1$'s, $0$'s or is empty.


Asymptotic estimate for $\sum_{k=1}^{N} {\frac{1}{k^2 H_k}}$

Since the infinite series $\sum_{k=1}^\infty \frac{1}{k^2H_k}$ converges, an asymptotic estimate to your sum is simply $\Theta(1)$.

You can obtain a better estimate by estimating the tail:
$$
\sum_{k=1}^n \frac{1}{k^2H_k} = \sum_{k=1}^\infty \frac{1}{k^2}{H_k} - \sum_{k=n+1}^\infty \frac{1}{k^2H_k}.
$$
We can estimate the tail by
$$
\sum_{k=n+1}^\infty \frac{1}{k^2H_k} \leq
\sum_{k=n+1}^\infty \frac{1}{k(k+1)} = \frac{1}{n},
$$
and so
$$
\sum_{k=1}^n \frac{1}{k^2 H_k} = C - O\left(\frac{1}{n}\right),
$$
where $C = \sum_{k=1}^\infty 1/k^2H_k \approx 1.33275$.


Finding a particular path in weighted tree

The idea is to find, for each vertex $i$, the first vertex $j_i > i$ such that the distance $d(i, j_i)$ between $i$ and $i_i$ is at least $k$.
Then, you can return the pair $(i, j_i)$ such that $d(i,j_i)=k$ and $j_i-i$ is minimized.
This takes $O(n)$ time once you notice that, for $i_1 < i_2$, $j_{i_1} \le j_{i_2}$.
In pseudocode, where $w(\ell, \ell+1)$ denotes the weight of edge $(\ell, \ell+1)$:
i = j = 1
best_i = 0
best_j = n
d = 0

while i != n:
  if d<k and j!=n:
    d = d + w(j, j+1)
    j=j+1
  else:
    d = d - w(i, i+1)
    i=i+1

  if d == k and j - i < best_j - best_i:
    best_i=i
    best_j=j

return best_i, best_j


How do I minimize the cost of some algorithm that performs some operation on a list?

First, let us understand in more simple terms what you are trying to do. You start with a list of $n$ integers. Then you are repeating $n-1$ times the following operation: take a pair of integers, and replace them with their sum; this costs you the value of the sum. The costs accumulate additively, and your goal is to minimize the total cost.

You can construct a tree from the $n-1$ steps, in the following way. You start with $n$ isolated nodes. When adding two integers, you join them to a new root which represents their sum. In the end, you will have a binary tree whose leaves are the $n$ original integers. You can check that the total cost is $\sum_i d_i x_i$, where $x_i$ is the $i$'th integer and $d_i$ is its depth in the tree (number of edges from root to leaf). (A cost of $x_i$ is incurred each time that you add an integer in whose product $x_i$ was involved.)

At this point we have exactly reached the problem solved by Huffman's algorithm, which is exactly the algorithm given by your hint. You can look up a proof of optimality in many sources.


Maximum Enclosing Circle of a Given Radius

I don't know how to solve this problem in $O(n^2)$ time, but an $O(n^2\log n)$ algorithm does exist.

Let $C(s_i)$ be the circle whose center is $s_i$, the $i$-th point, with radius $r$. It's not hard to find that the point set $P = \{p_0, p_1, \ldots, p_m\}$ can be enclosed by a circle with radius $r$ iff the intersection $I(P)$ of $C(p_0), C(p_1), \ldots, C(p_m)$ is not empty. Moreover, if $I(P)$ is not empty, there must be some points in $I(P)$ lay on some $\textbf{bd}C(p_i)$ (the boundary of $C(p_i)$). So for each $C(s_i)$ and each point $p$ on its bondary, we try to find how many circles contain $p$. The max count among all $p$ will be the answer to this problem.

Let's examine points in $\textbf{bd}C(s_i)$. There is an one-to-one mapping between the points on $\textbf{bd}C(s_i)$ and the real number in $[0, 2\pi)$. For each circle $C(s_j)$, the intersection between $C(s_j)$ and $\textbf{bd}C(s_i)$ can be represented by an interval $[begin_j, end_j]$. So for all circles other than $C(s_i)$, there are at most $n-1$ intervals (some circles may not intersect with $C(s_i)$). The max count can be found easily by sorting all $2(n-1)$ end points of interval, scanning them in order and counting the current overlapping number. For each $C(s_i)$, this step can be done in $O(n\log n)$ time, and there are $n$ such circles, so the time complexity of this algorithm is $O(n^2\log n)$.


Calculate maximum ammount of Bus Bandwidth

Start from the definition.  Bandwidth is defined as data transferred per unit time.  For instance, it's the number of bytes transferred, per second.

So, work out how many bytes it would be possible to transfer across the bus, in one second.  Forget formulas: just try to reason it through.  How many 32-bit words could you transfer in one second?  How many bytes does that correspond to?


Proof for P-complete is not closed under intersection

Let $A$ be any P-complete problem (say circuit evaluation). Here are two other P-complete problems: $A_0 = \{0x : x \in A \}$ and $A_1 = \{1x : x \in A\}$. The problem $A_0 \cap A_1 = \emptyset$, while definitely in P, isn't P-complete. The latter is true even if we allow Turing reductions, assuming $L \neq P$.


According to the WP article on Turing machine equivalents, oblivious machine head position is independent of input and is a function of time instead. To wit:

  An oblivious Turing machine is a Turing machine where movement of the various heads are [sic] fixed functions of time, independent of the input. In other words, there is a predetermined sequence in which the various tapes are scanned, advanced, and written to.

REFERENCES

https://dl.acm.org/citation.cfm?doid=322123.322138

SEE ALSO

Head Position Function of Oblivious Turing Machines
https://stackoverflow.com/questions/14847080/how-does-an-oblivious-turing-machine-work


Maintain statistics over a sliding window (robust & efficient)

To compute the mean of all the values in your window, separately compute (a) the sum of all the values in the window, and (b) a count of the number of values in the window.

To keep track of the sum of all the values in the sliding window, each time you receive a new value, add it to the sum.  Each time a value leaves the window, subtract it from the sum.  Now you'll always have a sum of the values in the window.

To keep track of the number of values in the window, each time you receive a new value, increment the counter.  Each time a value leaves the window, decrement the counter.

Finally, the mean is the sum divided by the count.

To keep track of the variance, you need the count, the sum of the values, and the sum of the squares of the values.  You can keep track of the sum of the squares of the values in the window in the same way (when a new value arrives, add its square to the running sum; when a value leaves, subtract its square).  These three values are enough to let you compute the variance of the values in the sliding window.

Note that when using the sum of squares method to compute the variance, you will need to compute the three intermediate values to enough digits of precision.  If you don't have enough digits of precision for those intermediate values, then you get a very inaccurate estimate.  This is the robustness problem that is mentioned in the blog post you link to and that is addressed by Welford's method.  However, there is another pragmatic way to address it that will work for most practical settings: just compute those three intermediate values to more digits of precision.

For the covariance between $x_1,\dots,x_n$ and $y_1,\dots,y_n$, you need to know the sum of the values $x_i$, $x_i^2$, $y_i^2$, $x_i y_i$, and the count $n$.  So, it's basically the same principle as above, but now there are five intermediate values you need to maintain, instead of just three.


Regular expression for $\{a^k b^m c^n \mid k+m+n \text{ is odd} \}$

What you need is that either exactly two of $k$, $m$, $n$ even, or all three odd, because two odds and an even make an even; and three evens make an even.

An odd number of $a$'s translates to the regular expression $a (a a)^*$, an even number to $(a a)^*$.

Pulling the above together:
$$
a (a a)^* (b b)^* (c c)^* \mid  (a a)^* b (b b)^* (c c)^* \mid (a a )^* (b b)^* c (c c)^* \mid a (a a)^* b (b b)^* c (c c)^*
$$


I just read the definitions, hence I am not an expert on LBAs, but I think that the non-emptiness problem $\overline{E_{LBA}}$ is r.e., so the emptiness problem $E_{LBA}$ can not be r.e., otherwise it would be decidable.

To see why $\overline{E_{LBA}}$ is r.e., notice that to certify that an $LBA$ has nonempty language it suffices to exhibit a word $w$ and a trace $t$ proving that $w$ is accepted by the $LBA$. So, a semidecider only has to enumerate all such pairs $(w,t)$, and (effectively) check for each pair if it proves the $LBA$'s language nonempty.


What is the fastest and most elegant way to change a matrix dimension?

I would consider a sentence such as this to be unambiguous:

We flattened the $h \times w \times 3$ input data down to a two-dimensional $hw \times 3$ shape.

I don't believe a reference explaining this would be necessary.


As a result, I can say that every NFA that can be constructed is decidable. Is this true?

Yes. An NFA can be converted to a deterministic finite automaton, and that can simply be run to decide the output.

  However, is it possible to find a Turing Machine that can accept w whose length is composite number?

Yes, this is possible. It follows from the fact that it can be done in any old Turing-complete programming language, hence also on a TM.

  Is it possible to construct a CFG that accepts this w?

I doubt it. Maybe there is a proof, but I do not see it right away.

Most problems you'll encounter in practice are decidable, because you can come up with an algorithm to decide the answer. If you want an example of an undecidable problem, have a look at this list on Wikipedia.


Why is abstraction in lambda calculus called abstraction?

Abstraction in the context of lambda calculi means turning some part of a term into a variable. Let's do an example. Consider the following terms (which use a notation richer than pure lambda calculus):

$1 + 2$
$\sin^2(\varphi) + \cos^2(\varphi)$
$\frac1{n + 1}t^{n + 1} + C$

They have one thing in common. They all are built from smaller terms using $+$. Now, if we want to abstract away from the details and focus on the general common property of these terms, we just turn everything that is not $+$ into variables and end up with $\lambda x.\lambda y.x + y$, a function abstraction (if that is the name your introductory text uses; I am more familiar with the name "lambda abstraction").


Lambda calculus :Will there be any x left after first substitution?

After $[Q/x]M$ we no longer find free occurrences of $x$ ... unless $x$ is free in $Q$! The simpler example is $Q=x$, where $[x/x]M=M$ can have free occurrences of $x$.

In such case, the free $x$s due to $Q$ can be replaced by $[P/x]$ in your example.

E.g. $[z/x][(\lambda y.\ x)/x](x(yx)) = ((\lambda y.\ z)(y(\lambda y.\ z)))$.

According to (e) we have indeed

$$
\begin{array}{l}
[z/x][(\lambda y.\ x)/x](x(yx)) \\
= [[z/x](\lambda y.\ x)/x](x(yx))\\
= [(\lambda y.\ z)/x](x(yx))\\
= ((\lambda y.\ z)(y(\lambda y.\ z)))
\end{array}
$$

Finally, note that when $x$ is not free in $Q$, we have
$[[P/x]Q/x]M = [Q/x]M$ as an immediate consequence of $[P/x]Q=Q$.


Amortized time of insertion into an Array list

The question might be a little misleading.

  So, after n elements inserted, we've resized at sizes 1, 2, 4, ... , n.

This is only true if $n = 2^k$ for some $k \in \mathbb{N}$, because for a growth factor of 2, we only need to resize when $n$ is a power of 2.

So in your case we would only resize at 1, 2, 4. Not 7.

You should keep in mind this only applies to a growth factor of 2. We could change the growth factor however we wish. For example we set the growth factor to 3. Then we resize at powers of 3; $\{1, 3, 9, \dots 3^k\}$. You can still use the same analysis procedure to get a constant amortized time though.


Time-slice multithreading is the convectional multithreading where CPU creates an illusion of executing more than once program at a time but the CPU can execute only one of these programs at a time. The OS maintains the illusion of concurrency by rapidly switching between running programs at a fixed interval, called a time slice. Time slice multithreading works similar to RoundRobin fashion.

For detailed understanding refer

Definition (Convectional multithreading)
Stackoverflow answer


Lower bound on approximation degree in Nisan-Szegedy

If you believe Lemma 3.8 for $\deg f$, you should also believe it for $\widetilde{\deg} f$. An earlier lemma states that if $f$ is a Boolean function on $n$ variables such that $f(\mathbf{0}) = 0$ and $f(\mathbf{x})=1$ for all $|\mathbf{x}|=1$ then $\deg f \geq \sqrt{n/2}$ and $\widetilde{\deg} f \geq \sqrt{n/6}$. Applying the first part of this lemma,  we conclude the first part of Lemma 3.8, namely $\deg f \geq \sqrt{\operatorname{bs}(f)/2}$. Applying the second part of this lemma, we conclude the second part of Lemma 3.8, namely $\widetilde{\deg} f \geq \sqrt{\operatorname{bs}(f)/6}$.


I read a survey paper a few years ago that seems relevant, "Successful SAT Encoding Techniques" by Magnus Björk.
Abstract:

This article identifies good practices for SAT encodings by analysing interviews with a number of well known SAT experts.  The purpose is both to determine the confidence in different encoding strategies by analysing whether there is consensus among the experts or not, as well as bringing out hidden knowledge to SAT users.
There is consensus that encoding techniques usually have a dramatic impact on the efficiency of the SAT solver, that it often takes much work to find a good encoding, and that the size of an enconding is only very loosely related to the hardness of finding a solution.  Topics where the interviewees disagree include the feasibility of including arithmetics in SAT problems and whether to formulate problems as clauses or circuits.
The article describes a number of strategies that are good in different situations, such as different ways to represent numbers and how to use incrementality.


How to eliminate context-free grammar's ambiguity

There is no general trick — indeed, given a context-free grammar, it is undecidable to determine whether it is ambiguous or not, and it is also undecidable to determine whether the language it generates is inherently ambiguous or not, see for example this answer on cstheory.

In your case, one way to go is to think of $a$ as corresponding to $\nearrow$ and of $b$ as corresponding to $\searrow$. We are interested in paths that start and end on the $x$ axis, for example
$$
\begin{array}{cccccc}
& \nearrow & \searrow \\
\nearrow & & & \searrow \\\hline
& & & & \searrow & \nearrow
\end{array}
$$
We can decompose every such non-empty path into a first part, which ends the first time that the path reaches back to the $x$ axis, and the rest. If the first part starts with $\nearrow$, then it ends with a $\searrow$ and in between there is a path which never dips below where it started. We can denote such a path by $\top$. Any such path is either empty, or can be decomposed into a first part ending when the path reaches back to the initial level, followed by another $\top$ part. Putting everything together (and consider also the case in which the first part starts with $\searrow$), we obtain the following unambiguous context-free grammar (which for brevity is over $\nearrow,\searrow$):
$$
\begin{align*}
& S \to \epsilon \mid \color{red}\nearrow \top \color{red}\searrow S \mid \color{red}\searrow \bot \color{red}\nearrow S \\
& \top \to \epsilon \mid \color{red}\nearrow \top \color{red}\searrow \top \\
& \bot \to \epsilon \mid \color{red} \searrow \bot \color{red}\nearrow \bot
\end{align*}
$$


Cont: NP-hard or not: partition with irrational input or parameter

Without answering your specific question, let me comment on a basic matter that I see appearing in several of your questions.   Trying to reason about this as "irrational parameters do or don't make the problem ill-defined" seems likely to be confusing.

Instead, back up and understand the fundamentals.  The fundamentals are that we need to specify a problem precisely before we can ask for its running time.  How do we specify a problem?  The most fundamental way is as a decision problem, and a decision problem is a formal language: a subset of $\{0,1\}^*$.  Thus, the problem is: given a string $x \in \{0,1\}^*$, answer whether it is in the language $L$.  More generally, if you want to discuss algorithms for problems that produce multiple bits of output, a problem specifies a function $f:\{0,1\}^* \to \{0,1\}^*$.  In other words, given any bit-string that is the input, the function $f$ tells us a bit-string that is the desired output.

So, to specify a problem carefully, you specify that mapping $f$.  Usually, this is done by specifying the input and how it is represented as a binary string (as a convenience, this latter step is often omitted if it is obvious how to do it, but it's exactly this step that is tripping you up, so for you, do not omit it), and by specifying the correct output (as a function of the input) and how it is represented as a binary string (again, you better not omit this).

When you start talking about irrational numbers, you are going to run into the problem that irrational numbers cannot be represented as a binary string.  There is no encoding of numbers that enables you to encode all possible irrational numbers and that ensures that all encodings are finite.  Thus, if your problem statement says "the input is an irrational number...", you are going to have a problem.

Then, to prove that a question is NP-complete, you construct a reduction.  So, go do that.  Don't try to prove it with one line ("there is one instance with rational inputs satisfying..") constructed in an ad-hoc way -- instead, explicitly construct the reduction.  If you understand the concepts, you should be able to tell whether your reduction is correct or not, without needing to ask us.

Before asking another in this line of questions, I suggest that you study basic material on P, NP, reductions, and complexity classes.  Make sure you understand it at the basic level, before trying to apply it to your specific problem.  Textbooks are written to make it easier to understand these concepts in the context of some simpler problems, and that will make it easier to pick up than to try to both learn the concepts and apply it to your harder problem at the same time.


One element that differs in two arrays. How to find it efficiently?

I see four main ways to solve this problem, with different running times:

$O(n^2)$ solution: this would be the solution that you propose. Note that, since the arrays are unsorted, deletion takes linear time. You carry out $n$ deletions; therefore, this algorithm takes quadratic time.
$O(n \: log \: n)$ solution: sort the arrays beforehand; then, perform a linear search to identify the distinct element. In this solution, the running time is dominated by the sorting operation, hence the $O(n \: log \: n)$ upper bound.

When you identify a solution to a problem, you should always ask yourself: can I do better? In this case, you can, making a clever use of data structures. Note that all you need to do is to iterate one array and perform repeated lookups in the other array. What data structure allows you to do lookups in (expected) constant time? You guessed right: a hash table.

$O(n)$ solution (expected): iterate the first array and store the elements in a hash table; then, perform a linear scan in the second array, looking up each element in the hash table. Return the element that is not found in the hash table. This linear-time solution works for any type of element that you can pass to a hash function (e.g., it would work similarly for arrays of strings).

If you want upper-bound guarantees and the arrays are strictly composed of integers, the best solution is, probably, the one suggested by Tobi Alafin (even though this solution will not give you the index of the element that differs in the second array):

$O(n)$ solution (guaranteed): sum up the elements of the first array. Then, sum up the elements of the second array. Finally, perform the substraction. Note that this solution can actually be generalized to any data type whose values can be represented as fixed-length bit strings, thanks to the bitwise XOR operator. This is thoroughly explained in Ilmari Karonen's answer.

Finally, another possibility (under the same assumption of integer arrays) would be to use a linear-time sorting algortihm such as counting sort. This would reduce the running time of the sorting-based solution from $O(n \: log \: n)$ to $O(n)$.


Merge two series of sorted number, one much longer than the other

What exactly does $n \gg m$ mean for your professor?

If it means $m \in o(n)$, then you are allowed $O(\log m)$ time for step 2.2. Note that $\log(n/m) = \log n - \log m$. If $m \in o(n)$, the target runtime bound simplifies to $O(m \log n)$; a summand $m \log m$ is dominated by this.

If $m \in \Theta(n)$ is allowed -- arguably, $m = n \cdot 10^{-10}$ would fulfill "a lot smaller" -- you can have that  $\log n/m \in O(1)$ and the runtime bound is $O(m)$. It's quite clearly impossible to perform this task in time $O(m)$, so I think we can safely ignore this case for the purpose of this exercise.

But here is something more for you to think about.

In step 1, you need to specify "special"; if you don't pick the elements according to your sketch, the rest won't work out. So we have to select the elements $i(n/m)$. In order to do this in $o(n)$ time and perform binary search efficiently, we need the series to be stored as arrays.

We can not copy all values to a new array in the required time. We can not insert values into an array, either. So how is this to work at all?


Implications of the $\Omega(\frac{2^n}{n})$ circuit lower bound being tight

This has been proved by Muller as early as 1956. Here is the construction. Let $k$ be a parameter. We first compute all possible functions on the first $k$ inputs in size $O(2^{2^k})$ (see below). We then construct a decision tree for the other $n-k$ variables, connecting it to the correct function on the remaining variables. This takes $O(2^{n-k})$ (see below), for a total of $O(2^{2^k}) + O(2^{n-k})$. Choosing $k = \log (n - \log n)$, we obtain the desired bound.

We compute all possible functions on $k$ inputs inductively. Let $Z_k$ be the size of a circuit computing all possible functions on $k$ inputs. There are two functions on zero inputs, so $Z_0 = 2$. Every function $f(x_1,\ldots,x_k)$ on $k$ inputs can be written as $x_k f(x_1,\ldots,x_{k-1},1) + \overline{x_k} f(x_1,\ldots,x_{k-1},0)$, so $Z_k = Z_{k-1} + 2^{2^k} \cdot O(1)$. The solution of this recurrence is $Z_k = O(2^{2^k})$.

In order to compute the decision tree, we use a similar construction: given a tree $T$ for the first $k-1$ variables, we can construct a tree for the first $k$ variables of the form $x_k T + \overline{x_k} T$. The recurrence we get is $W_k = 2W_{k-1} + O(1)$, whose solution is $W_k = O(2^k)$.


Can nfa consume more than one letter at a time

Yes, as long as your alphabet is defined as a set of different couples of binary digits


"Equality" problem in distributed computation

This is probably referring to the communication complexity of the function $f(x,y) = 1$ if $x=y$ and $f(x,y) = 0$ if $x \ne y$.  See https://en.wikipedia.org/wiki/Communication_complexity#Example:_%7F'%22%60UNIQ--postMath-00000031-QINU%60%22'%7F for the formulation and a proof of the lower bound.


Maintaining balanced BSTs in order to get $\frac{n}{2}$ largest elements in constant time

Maintain two BSTs $T_1$ and $T_2$ such that $T_2$ always contains the largest $\lfloor n/2 \rfloor$ elements, and $T_1$ contains the remaining elements.
Insertions and deletions can be implemented in $O(\log n)$ time by performing the corresponding operation in a suitably chosen tree and then moving at most one element from one tree to the other.
For example, to insert an element $x$ proceed as follows:

Find maximum element $m$ of $T_1$
If $x \le m$:

Insert $x$ in $T_1$
If $|T_2| \neq \lfloor n/2 \rfloor$:

Delete $m$ from $T_1$
Insert $m$ in $T_2$

Otherwise:

Insert $x$ in $T_2$
If $|T_2| \neq \lfloor n/2 \rfloor$:

Find the minimum element $m'$ of $T_2$
Delete $m'$ from $T_2$
Insert $m'$ in $T_1$

Deletions are handled similarily.
The same approach also works if you maintain two heaps (a max-heap and a min-heap) instead of two BSTs.
See also this answer that uses a similar idea.


Is there an algorithm that can ensure everyone gets bussed to their destination on time, while minimizing the time spent on a bus?

This problem is NP-hard. You can reduce the Hamiltonian-Cycle problem to this problem.  Given an instance of the Hamiltonian-Cycle problem, fix a vertex $v$. Assume there is exactly one bus and $2n - 2$ passengers, where $n$ is the number of vertices in the graph. We set the passengers such that one passenger wants to travel from $v$ to each other city in the graph and one to travel from each other vertex to $v$.
Claim. The given graph admits a Hamiltonian-Cycle, if and only if the total travelled distance is $2\frac{n (n-1)}{2}$.
Proof. An optimal route is a Hamiltonian-Cycle from $v$ [try to see why]


Range of values for Kolmogorov complexity

The answer depends on the exact choice of program description language. We can define Kolmogorov complexity with respect to any admissible program description language. A program description language $L$ is admissible if for all program description languages $L'$, we have $K_L(x) \leq K_{L'}(x) + C_{L'}$, for some constant $C_{L'}$ depending only on $L'$.

We start by showing how to construct an admissible program description language in which all Kolmogorov complexities are even. Let $L$ be an admissible program description language. We define a new program description language $L'$ as follows: if $|x|$ is odd or $x = \epsilon$ then $L'(x) = \epsilon$; if $|x|$ is even and $x=0y$ then $L'(x) = L(y)$; and if $|x|$ is even and $x=1y$ then $L'(x) = L(z)$, where $z$ is obtained from $y$ by removing the last symbol. Since $K_{L'}(x) \leq K_L(x) + 2$, $L'$ is admissible. On the other hand, it is easy to check that $K_{L'}$ is always even.

Conversely, we can also arrange that all Kolmogorov complexities would be achieved.  Let $L$ be an admissible program description language. We construct a new admissible program description language $L'$ as follows: $L'(\epsilon) = z$, where $z$ is some string satisfying $K_L(z) < |z|$ (we can choose $z = 0^{2^n}$ for large enough $n$); $L'(0x) = x$; and $L'(1x) = L(x)$. Then $K_{L'}(z) = 0$, and for $w \neq z$, we have $K_{L'}(w) = \min(|w|,K_L(w)) + 1$. For every $n \geq 1$, we can find a string $w$ of length $n-1$ such that $K_L(w) \geq n-1$. This string satisfies $K_{L'}(w) = n$.


Algorithm for arranging elements into different sized buckets

Your problem can be solved in polynomial time.

You mention two possible goals and say you'd be happy with a  solution to either.  The first goal isn't well-defined, so I'll describe a solution to the second goal.  I can see two possible approaches: (a) use integer linear programming (ILP), (b) use network flow.  The former will be simple to implement, and is flexible (if you later have new constraints it'll be easy to add them), but if you're unlucky, the running time could be exponential.  The second has the advantage of running in polynomial time, but it might be more work to implement.  fade2black described the ILP approach well, so I'll describe the network flow approach.

To solve the problem with network flow, formulate this as a minimum-cost network circulation problem.  In network flow, each edge has a capacity: an upper bound on the amount of flow through that edge.  Minimum-cost circulation also allows you to specify a lower bound on the amount of flow through that edge, and the per-unit cost of sending flow through that edge.

We'll construct a directed graph with a source node $s$, a node $u_i$ for each item, a node $v_j$ for each buyer, and a sink node $t$.  Add edges $s \to u_i$ with cost 0, lower bound $1$, and upper bound (capacity) $1$.  Add edges $u_i \to v_j$ with cost equal to the negative of the amount buyer $j$ will pay for item $i$, lower bound $0$,  and upper bound (capacity) $1$.  Add edges $v_j \to t$ with cost 0, lower bound equal to the quota for buyer $j$, and upper bound $\infty$.  Finally, add an edge $t \to s$ with cost 0, lower bound 0, and upper bound $\infty$.  Now look for the minimum-cost circulation in this graph.  That will correspond to a solution that maximizes the revenue, subject to the requirement that all quotas must be filled.


Response time of scheduling a DAG where each vertex is a task

Found it! This problem is NP-complete when the goal is to minimize total execution time.

The scheduling problem (P1) is the following. We are given
(1) a set $S = \{J_1 , \ldots , J_n\}$ of jobs,
(2) a partial order $\prec$ on $S$,
(3) a weighting function $W$ from $S$ to the positive integers, giving the number of time units required by each job, and
(4) a number of processors, $k$.

Please see the following paper, which immediately discusses it from the introduction onward:
J.D. Ullman. Np-complete scheduling problems. Journal of Computer andSystem Sciences, 10(3):384 – 393, 1975.
There are a few other cases that may be of interest that are discussed in the paper:

When $\prec$ is empty (no edges in the DAG)
(P2) When $W(J_i) = 1$ for all $i$.
(P3) When $k = 2$ and $W(J_i) \in \{1, 2\}$ for all $i$.

You can show 3-SAT reduces to (P2) through and intermediate problem (P4) that Ullman discusses. Then it is clear that (P2) reduces to (P1).


How to convert DFA to regex with State Elimination

If we're talking about the same Elimination problem then you should add an accept state and a start state. In addition, I allowed myself to disregard state $q_b$ as it never part of the language.

The start state will replace $q_0$. The accept state will replace $q_9$. Then to your request, we'll do the rest, starting from $q_1$.

From $q_1$ you either have 0 endless times or a 1 in other words, $0^* \cup1$ from $q_1$ to $q_2$.

Let us now rip $q_3$: from $q_2$ to $q_4$ you'll need 01. While from $q_4$ to $q_1$ you'll need 00.

Proceeding to rip $\{q_0, q_2\}$, note this is no more than a name and could just as well be renamed to $q_5$. Thus from $q_2$ to $q_1$ we have: $11*0$

All that's left is to close the circles which are probably cause your trouble:
For the fun of it, we'll go by order. Let us rip $q_1$:
This means $q_0$ reaches $q_2$ using a concatenation of 0 with the resulting regex of $q_1$ to $q_2$ which is we found and was $0^*1$. Removing $q_1$ then completes the self-cycle of $q_2$ and there would now be an arrow to self: $11^*0$.

Nearly done, remove $q_2$: remove $q_2$ thus connecting $q_0$ to $q_4$ through $0((0^*1)11^*0)^*01$, however, there are also the loops that are created to be taken into account, see the drawing attached: I realized that this is very confusing to read so I've added the following drawing:

I might have missed a character or two, but those are my two cents, also- remember to keep the loops in mind and their final transitions.

P.s. I noticed in the second NFA (yes, NFA as there are $\epsilon$ transitions), I have accidentally forgotten to add the transition itself from $q_2$ to $q_1$, however it is there in the next NFA


How to write a coterminating, effectful program?

In these sorts of cases, one idiomatic way is to run it with gas, and to create one non-total gas value to let you finish the program. Yes, perhaps Idris should offer a combinator for IO that allows full streams to be run, but this is sufficient, and doesn't affect the validity of anything else.

Seeing this, I'd agree that the IO monad should be coinductive, not inductive.

%default total

data Gas : Type where
  More : Lazy Gas -> Gas
  Done : Gas

runStream : Gas -> Stream (IO ()) -> IO ()
runStream (More g) (i :: is) = i >>= \_ => runStream g is
runStream Done _ = pure ()

partial
unbounded : Gas
unbounded = More unbounded


Find which bundles can be demanded together

This can be solved in polynomial time, by solving $2^{2m}$ linear programs.  (That might look exponential, but is polynomial in the size of the input, as the input size is $2^m$.)

Given a pair of bundles, you can check whether it is a demand-pair using linear programming; see below.  So, you can apply this to all candidate pairs.

Suppose we have two bundles, $X,Y$, and we want to know if they are a demand-pair.  Introduce a variable $p_x$ for each $x \in M$.  It's easy to write a linear equality that expresses that $X,Y$ have the same net-utility: $u(X)=u(Y)$.  Also, it's easy to write linear inequalities to express that no other bundle has higher net-utility: $u(X) \ge u(Z)$ for all other bundles $Z$.  Each of those is a linear (in)equality on the variables $p_x$.  We also have the inequalities $p_x \ge 0$.  Now use linear programming to test whether all of those inequalities are simultaneously satisfiable; if they are, there exists a price-vector where $X,Y$ are simultaneously demanded.

As an optimization, note that $X,Y$ are a demand-pair for market $M$ iff they are a demand-pair for market $X \cup Y$: without loss of generality you can set the price of every item in $(X \cup Y) \setminus M$ to $+\infty$.  Also, without loss of generality you can set the price of every item in $X \cap Y$ to 0.  Consequently, $X,Y$ is a demand-pair for market $M$ iff $X'=X \setminus Y$ and $Y'=Y \setminus X$ are a demand-pair for market $X' \cup Y'$.  This will make each linear program smaller and more efficient to solve.  It also means that you only need to test pairs that have no common intersection, so it suffices to test at most $3^m$ pairs $X',Y'$.


How can I make a pipeline with undefined/unlimited stages?

The thing about the MIPS/DLX-ish pipeline that you're probably talking about is that all of the pipeline control is central. There is a pipeline/hazard circuit which knows what's going on everywhere, and it does all the hard work.

This is probably why you asked the question: you can already see that there is no way this will scale!

There are three main techniques to construct a deep pipeline:

Nest pipelines and use hierarchical control.
Eliminate central control by making control as local as possible.
Reduce the need for control by designing the pipeline so that some situations that would require control never happen, or turn into an easier-to-handle control situation.

We'll take a look at these in turn, but bear in mind that all of these techniques can be mixed and matched as appropriate.

Hierarchical control

This is the simplest modification to what you've already seen. The idea here is that each logical unit in a CPU (e.g. instruction fetch unit, integer unit, load/store unit) may be a small pipeline by itself. Then you can decide what control needs to happen within that unit and what control needs to happen between units.

If you think about an instruction fetch unit, for example, there are various reasons why it might stall: it might be experiencing a cache miss, it might be recovering from a mispredicted branch, or whatever. In many situations, the control for the core as a whole may not care why the IFU is stalling, it only matters that it is stalling, because that means it isn't supplying instructions to the next stage. So the IFU may implement its own control, and communicate with higher-level control using coarser signals.

An extreme example of this is to use a coprocessor design. Coprocessors don't have to be on separate chips; the MIPS architecture uses a coprocessor for the MMU, for example. It isn't really a separate processor, but it is wired up to the core's control system as if it were.

This was an especially popular technique back in the day when CPUs came on more than one physical die such as POWER1.

Local control

Based on the previous idea, another way of coordinating different units is to just let them communicate with their surrounding units. There will probably still need to be some central control, but this could be reserved for large-scale events such as recovering from a fault or bad speculation.

So, for example, a unit which can't take any more work at the moment (whether it's because it's doing a multi-cycle operation, stalled on a cache miss, or stalled because the unit it needs to send a result to is itself busy) might simply provide a signal which says "I cannot take any more work right now". Any unit which wants to feed it work looks for that signal.

Another example of something that could reasonably be called "local control" is to use busses with arbitration. You can move data through the CPU using busses, and if two units want to write to the same bus at the same time, they decide between them that one will back off. You might use this in a Tomasulo pipeline.

An extreme example of local control is the counterflow pipeline. This is an example of a pipeline which can be arbitrarily deep using only local control, to the point where the pipeline could in principle be made completely asynchronous.

Redesign

If it is possible to eliminate the need for control by redesigning the pipeline, this is always worth considering. The classic example is register renaming, which effectively eliminates WAR hazards for registers. If a hazard is impossible, there doesn't need to be any control for it!

There are endless variations on this theme. For example, register renaming when there aren't "enough" physical registers available turns the WAR hazard into a stall in the rename stage. A stall early in the pipeline may be easier to control than a hazard late in a deep pipeline, because there are fewer cases to consider.

Another variation is to use speculation with a general recovery mechanism. If you think of a SPARC/MIPS-like pipeline, there is a delay slot after every branch, which is only possible because the pipeline is short. In a deeper pipeline, the most common solution is to speculate the branch and then use a general pipeline recovery mechanism if we got it wrong.

It's a similar story with instructions that could fault. Any memory access could cause a page fault. Any division could be a division by zero. We effectively "speculate" that this didn't happen, and fall back on the general recovery mechanism if it actually did. That way we don't need special control for a page fault.

A good place to start on this is Mike Johnson's book Superscalar Microprocessor Design (1991). It's old but it's full of good stuff that explains how these sorts of things actually work in practice.