What are the flaws in this encryption algorithm? Let $A$ be a randomly generated matrix. Let $I$ be the identity matrix. $\times$ is the matrix multiplication operation, $/$ is matrix division (multiplying the first matrix by the inverse of the second).
$$
I \times A \times A = B
$$

Provide $B$ and $I$ to the recipient. To create encrypted message $E$ from unencrypted message $M$:
$$
E = M \times A \times A
$$

Send $E$ to the recipient. The recipient will solve for $M$ using:
$$
M = E / ( B / I)
$$
My question is:

Will the recipient be able to decode the message?
If an attacker knows $E$ and $I$, can they efficiently solve for $M$?
Is there a simple way to make it nonlinear?

I accepted an answer but am still waiting for #3.

This is not a secure encryption scheme.  It is similar to a Hill cipher, and vulnerable to similar attacks.  For instance, it is vulnerable to known-plaintext attacks: an attacker who observes a ciphertext E and knows the corresponding message M can recover the secret key and thus decrypt all other messages that were encrypted with the same key.

The recipient will be able to decrypt if A is invertible.  If A is not invertible, then the recipient won't be able to decrypt.

See also the questions about the Hill cipher on Crypto.SE.


What is the growth rate of the world wide web? Is there any way to estimate how much data is added to the world wide web each second? Are there any studies about this?

There is much interesting research in this area that is ongoing. See eg

Using search engines to estimate size based on pages counted eg How Large is the WWW by Dobra and Fienberg
Theoretical models of networks that model the growth of the web and reflect its small world graph structure eg Models for the Growth of the Web by Ho, Pu, Tsiatas


Is it possible for a language and its complement to both be unrecognizable? Given some unrecognizable language $L$, is it possible for its complement $\overline{L}$ to also be unrecognizable?

If some other language $S$ and its complement $\overline{S}$ are both recognizable, then $S$ and $\overline{S}$ are decidable. If $\overline{S}$ is unrecognizable, then then $S$ is undecidable but still recognizable. Why do we ignore the idea that $S$ and $\overline{S}$ may both be unrecognizable? This implies that $\exists! s \in S \cup \overline{S} = \Sigma^*$ on which no machine halts, otherwise I don't see why we cannot have $x,y \in \Sigma^*$ and $x \neq y$ such that no machine halts on $x$ or $y$, where $x \in S$ and $y \in \overline{S}$.

Perhaps I am making a false assumption somewhere?

I'll write "corecognizable" as a shortcut for "complement of recognizable". There are countably many recognizable languages and countably many corecognizable languages. Therefore, there are uncountably many languages which are neither recognizable nor corecognizable.


What is the meaning of uniform distribution of elements in an array? I was going through the concept of Interpolation search and it stated that when the elements are "uniformly distributed", it takes O(loglogn) to search an element using interpolation search. Can someone please explain me this?

Suppose that the array $A$ is chosen in the following way:

Sample $n$ real numbers uniformly from the interval $[0,1]$.
Sort the $n$ samples.

Suppose that you choose a further uniform random variable $x$ from the interval $[0,1]$. The expected running time of interpolation search on $A$ and $x$ is $O(\log\log n)$, where the expectation is over the choices of both $A$ and $x$.

In fact, if I understand Gonnet's thesis correctly, the expectation is still $O(\log\log n)$ even for any fixed $x$. See also Gonnet et al.


Optimal way for the remainder I want to know if for any base the most significant digit is 1 or not.
Here is the code:

for(int i=3;i<=a;i++)
  {
    int x = i;
    int r = a;
    while(r/x)
    {
      r = r/x;
    }
    int rem = r%x;
    if(r==1)
    {
      count++;
    }
  }

is there any optimal way to replace the while loop nested in the for loop.

You would pick some number a, run the code, and see if you can find a pattern. There will be an obvious pattern. Then you think how you can use that pattern to find long ranges of numbers i where r ends up being 1, and long ranges where r does not end up being 1.

When you've done that, all you do is add up the number of values in those ranges of values i that end up being 1.

The best way unless you are a super genius (in which case you wouldn't be asking here) is to play around with the code, figure out its behaviour, and think about ways to take shortcuts.


Self-Study of Computer Science I am a 16 year old male who has recently been gifted a big encyclopedia on computer science by a friend of mine. I am usually not that interested in computers and technology, but computer science has started to fascinate me. I do however intend to study Physics and/or Mathematics and not CS, so my question is, would it be useful to conduct a self-study of computer science? I'm not of course going for the level of a BSc but just the basics of CS (it is an encyclopedia with ~600 pages).

I think that learning about computer science certainly can be an advantage. Here are a number of (related) skills computer science has to offer.

Programming – knowing how to program is a useful skill for any discipline. Statisticians and sociologists, geographers and engineers, and so on, often find themselves needing to program. Following a CS degree should teach you to program properly.
Modelling – one of the key things computer scientists do is modelling the world. True, physicists, biologies and sociologists do too, but the kinds of models they are different. Knowing about the kinds of models computer scientists build can often help modelling in other disciplines. Even better, computer science models are generally executable (see point 1).
Abstraction – computer science is all about abstraction, ignoring irrelevant details to bring out the core of a problem. When modelling a programming language, not every single detail is modelled. One can abstract away from almost all details and study the concurrency model in isolation or just the classes in an object-oriented language. This kind of abstraction is less common in other sciences (I claim), but they are crucial for understanding phenomena computer scientists are interested in. I'm sure that other fields could benefit from some abstraction.

This is probably best summed up in an article about Computational thinking by Jeannette Wing.


Proof of an Optimal substructure in Dynammic Programming? Could someone please explain how exactly the proof of optimal substructure property in dynamic programming problems works?

They usually say:

  Let's say the global optimal solution is A, and B is part of the solution. So B must the optimal solution of the subproblem, because if it weren't, then A wouldn't be the global optimal.

It makes some  sense to me, but I think this would work with any non-dynamic problem (the property), or maybe it is because I still don't get how it works.

Can someone please help? How does the contradiction work?

There is no (one) formal definition of "optimal substructure" (or the Bellman optimality criterion) so you can not possibly hope to (formally) prove you have it.

You should do the following:

Set up your (candidate) dynamic programming recurrence.
Prove it correct by induction.
Formulate the (iterative, memoizing) algorithm following the recurrence.


Algorithmic challenge: generate a list of random non overlapping squares For an undisclosed reason, I need a list of $n$ squares in a two dimensions space where each square does not overlap.
So the challenge is simply: given a two dimensional area $a$ (topLeft: int, topRight: int, width: int, height:int), a number of squares required $n$ and a size for each square $s$: generate a list $L$ of $|L|=n$ squares in $a$ where the following condition holds.
$$\forall q,r \in L , q \neq r \implies \textrm{no_overlap}(q,r) \land \textrm{inside}(q,a)  $$
where no_overlap is a function that checks if square $q$ and $r$ do not overlap given the size $s$ and inside(q,a) checks if square $q$ is completely inside the area $a$.
I tried coming up with a solution myself but the only thing I can find is to brute force generating a square, check if there is overlap and if not ,add it to $L$. But as one might see, this algorithm could theoretically run forever. I would need something which is guaranteed to work in a finite time and preferably be of a complexity of at most $\mathcal{O}(n^2)$. So I thought to myself, maybe I could share this with other people around the world and see what clever ideas they have in mind. I most certainly find it an interesing theoretical question to ask. The practical reason is for a Unity 3D (game) project I am making.
EDIT:
This would be a possible solution graphically illustrated for $n=7$

You could perhaps use a 2 dimensional k-d tree to store the set of free positions $(x, y)$ where the left upper corner of a new square could be chosen without overlapping the existing squares. Each node of the tree covers a region in the area $a$ and you can decorate this node with this region's coordinate and the number of free positions that it contains. At the top of the tree, you can read the total number of available slots and simply choose a random number to get the index of that slot. By walking downwards in the tree, you can find which slot corresponds to this random number, then update the tree accordingly to add a new square.
My intuition is that the amount of data contained in the tree is approximately proportional to the number $k$ of squares already chosen and that the addition of a new square should be proportional to $\log k$ on average.
Edit: I wrote a working implementation in python 3 by using a tree structure. I'm not sure about the performance for large $n$ but it could  already be measured experimentally. I didn't make any effort to balance the tree but as new squares are chosen randomly, this randomness should balance the tree on average.
Here is a link to the program. I don't know if I can paste it in this post. It chooses randomly at most 10 squares that don't touch each other. Here is an example output


What sort of algorithm/communication model/data structure do collaborative real time editors use? I am researching collaborative editing systems for some work, but so far my search is turning up blank.

Collaborative real-time editing systems almost all have features like:

Many users can edit the document at the same time
All changes are dated and saved in a linear revision history
Edits are visible in semi-real time
Who-wrote-what is tracked for all content

I cannot think of a data- and procedure model to encompass all of these without huge inefficiencies, for example:

Take user input as a few typestrokes at a time, thus enabling real-time visibility but with horrible server loads.
Take user input as element changes, thus disabling real-time visibility and complicating many-user-editing of one paragraph.
Edit a XML Document Model Object in place responding to inputs, but making it difficult to version/revision track.
Edit linear text stored in an appropriate editing structure responding to inputs, making it difficult to verify that correct markup is being generated.
Store revision history accumulating, requiring computational resources but easing on space.
Store revision history whole, requiring space but easing on computation.

Am I off track? Does there exist good solutions to these problems? What, if any, is the relevant litterature?

The usual approach is operational transformation. The wikipedia page seems to be pretty good. Here are some other references:

Understanding and Applying Operational Transformation
Operational Transformation: An Introduction
OT FAQ
ShareJS - javascript library implementing OT

Here's a paper on a different approach: Real time group editors without operational transformation. (Note: I haven't actually read it, so can't speak to how good it is)


Possible solutions how to find all points (given by lat, long) that are within a radius from main point let's say that I have:

M - Main point - given by coordinates (lat, long)
C - Collection of points - also given by coordinates (lat, long)
R - Radius - maximum search distance

I'm trying to find all points that are within a radius from main point (neighbors).

algorithm(main_point, collection_of_points, radius) --> neighbors

Obvious solution is to calculate distances and select those points, where distance is equal or smaller than R, but I believe there are better options with better performance.

Do you know any possible solutions? I'm open for every idea (not only the best one).

EDIT:

I should add that I'm looking for solution where points are strongly dynamic (every point is mobile phone or car). I'd like to update point when it's neccessary (it has been moved) so frequency of updates depends on amount of connected devices (so as queries). Let's say that server will get update request every 5 second and query request every 20 second.

Visualisation

You can speed up your search by using a datastructure like a kd-tree or an r-tree. The basic idea is to divide your space into boxes and store the mapping from points to boxes (and back) in a way that allows for quick lookup times. Then you don't have to calculate the distances to all points to see which are too far away, you can restrict your search to points in the same (or adjacent) boxes.

But note that the naive approach is actually pretty good in this case, even if it's asymptotically not optimal. CPUs are really good at summing squares and it's trivial to throw more cores at the problem if you need more speed. So unless you're dealing with many points, it will be hard to beat.


Removing Epsilon Transitions? I've run into a problem concerning epsilon transitions and removing them. Specifically, it is to do with the picture seen in this post. My problem is that I am unsure of what to do with q1. I've already attempted to solve it but I don't know if it's correct.
Should it just sit there still with no inputs going to it essentially making it a dead state? What should its loop be that was once an epsilon loop?

Thanks, all help appreciated!

In the original automaton, there is no way to be in $q_1$, read one symbol, and end up in $q_1$, so in the resulting automaton, there is no loop on $q_1$.


How does paxos algorithm handle partial failures of accept messages? I've been reading the basic paxos algorithm from the "Paxos Made Simple" paper. I can't understand how paxos algorithm maintains the safety properties under partial failures of the accept messages, meaning cases where the proposer receives prepare responses from a majority, but the subsequent accept message does not reach all the acceptors. It seems to me this could lead in a violation of the safety properties, where there will be no majority that has agreed on the same value.

I created a contrived example of the use-case I am thinking about. In every round, the proposer sends a prepare message to a majority of nodes, gets a response from all of them, but then the accept message arrives only to one of them (the other ones get lost). More specifically, as shown in the image below:

in round 1, the proposer sends a propose (1) message. The acceptors haven't received any prepare message yet, so they all reply with a promise. The proposer gets a majority in phase 1, so sends an accept(1, A) message. This message reaches the first node that accepts it.
in round 2, the proposer sends a propose (2) message to a majority, which does not contain the node that has accepted a value. As a result, the proposes gets a majority and sends an accept(2, B) message, which reaches only the second node.
the round 3 is similar, where none of the selected acceptors during the first phase have accepted any value yet. As a result, the proposer picks a value and sends an accept(3, C) message, which reaches only the third node.
in round 4, the majority has to contain at least one of the acceptors that has accepted a value. Let's say this is the first node that has accepted the value A, which returns the number of the proposal (1) as a reply to the prepare(4) message the proposer sent. Since there's only one accepted value, the proposer uses this one and sends an accept(4, A) message, which reaches the fourth node.
in round 5, the proposer sends a propose(5) message to a majority that contains the first 2 nodes, which have accepted the values A and B. They both return the associated proposal numbers (1 and 2). The proposer picks the value corresponding to the highest one, B. The proposer then sends an accept(5, B) message, which only reaches the fifth node.

At this point, there is no way to satisfy the safety property, since we would need a majority (6/2 + 1 = 4) of acceptors to have accepted the same value.

Where is the flaw in my thinking ?

The paper's specification for the phase 2(b) of the algorithm, which is how an acceptor responds to an accept message is the following:

  If an acceptor receives an accept request for a proposal numbered n,
  it accepts the proposal unless it has already responded to a prepare
  request having a number greater than n.

This means that acceptors are allowed to accept multiple proposals (even with different values) in a single instance of Paxos, as long as they have not responded to a prepare request with a number greater than the number of the accept message. As a result, even after the last row of the example, a proposer could bring the system to an agreement, by making some of the nodes accept a different value.

For example, the proposer could send a subsequent prepare(6) message to nodes 1,2,5,6, followed by an accept(6, B) that reaches everyone, thus reaching a majority and concluding the consensus. The important thing to note is that after this point, it's impossible to form a majority with a different value, because any potential majority quorum would contain at least one node returning (6, B) during the prepare phase.


How to find a cut in a graph with additional constraints? I have a complete undirected graph $G=(V,E)$ with positive non-null rational weights $c:E \to \mathbb{Q}^+_{*}$ on the edges, such that $c(v,v) = 0$ for all $v$, and a subset $C \subset V$.
I would like to find (if it exists) a subset $S \subset V$ such that $\delta(S) < 2$, $S$ contains at least one vertex of $C$, and $S \ne C$.  Here $\delta(S)$ represents the sum of the weights of the edges that cross the cut $(S, V \setminus S)$.
Is there a polynomial-time algorithm for this problem?
I have thought of two possible approaches:

Create a new graph $G'$ using as edge weights $c'(v,w) = -c(v,w)$ and adapt (by updating some LP formulation or DP approach) the max-cut optimization version to this case;
Reduce this problem in the problem of partitioning $V$ into two vertex sets $X,Y$ so that the sum of the weights of the edges crossing the cut is < 2, and $X$ and $Y$ each contain at least one vertex of $C$. However, I couldn't think of any approach to solve this problem, yet.

I know the max-cut problem is hard, which makes me wonder whether there is a polynomial-time algorithm for this problem.
Remark: The proposed solution does not need to follow the presented approaches, they are presented just to help the reader.
I am facing this problem in a fractional separation routine of a routing MILP formulation.

The problem can be solved in polynomial time.  Here is one algorithm:

For each $s \in C$ and each $t \in V \setminus C$ such that $s \neq t$:

Find the minimum-cost $(s,t)$-cut.   By the max-flow min-cut theorem, this can be done in polynomial time using any maximum flow algorithm.

If the cost of this cut is < 2, output it and halt.

For each $s_0 \in C$ and each $s_1 \in V \setminus C$ and each $t \in V \setminus \{s_0,s_1\}$:

Find the minimum-cost cut that contains both $s_0$ and $s_1$ in the left part and $t$ in the right part.  This can be done in polynomial time by modifying the graph to merge the two vertices $s_0,s_1$ into a new vertex $s'$, then finding a minimum $(s',t)$-cut in the modified graph.

If the cost of this cut is < 2, output it (replacing $s'$ with $s_0,s_1$) and halt.

If you reach this point without halting, output that no such cut exists.

There may be more efficient algorithms by modifying algorithms for min-cut instead of min $(s,t)$-cut.  I don't know.  However, this suffices to show that the problem can be solved in polynomial time.

Proof of correctness: Suppose a cut $(S,V \setminus S)$ of the desired form exists.  Then there are only two ways we can have $S \ne C$:

Case 1: $C \setminus S \ne \emptyset$: In this case, pick any vertex in $C \cap S$ and call it $s^*$ (this can be done since $C \cap S \ne \emptyset$) and pick any vertex in $C \setminus S$ and call it $t^*$ (this can be done since $C \setminus S \ne \emptyset$).  Consider the minimum-cost $(s^*,t^*)$-cut, $(S^*,T^*)$.  By construction, $S^*$ has at least one element of $C$ (since $s^* \in S^*$) and $S^* \ne C$ (since $t^* \notin S^*$) and $\delta(S^*) \le \delta(S) < 2$, so $(S^*,T^*)$ is a valid solution to your problem.  Moreover, it will be found by one of the iterations of the first for-loop, namely, when $s=s^*$ and $t=t^*$, so the algorithm will correctly find a solution.

Case 2: $S \setminus C \ne \emptyset$: In this case pick any vertex in $S \setminus C$ and call it $s^*_1$ (this can be done since $S \setminus C \ne \emptyset$), pick any vertex in $S \cap C$ and call it $s^*_0$ (this can be done since $S \cap C \ne \emptyset$), and pick any vertex in $V \setminus S$ and call it $t^*$ (this can be done since $S \ne V$).  Consider the minimum-cost cut $(S^*,T^*)$ such that $s^*_0 \in S^*$, $s^*_1 \in S^*$, and $t^* \in T^*$.  By construction, $S^*$ has at least one element of $C$ (since $s^*_0 \in S^*$) and $S^* \ne C$ (since $s^*_1 \in S^*$) and $\delta(S^*) \le \delta(S) < 2$, so $(S^*,T^*)$ is a valid solution to your problem.  Moreover, it will be found by one of the iterations of the second for-loop, namely, when $s_0=s^*_0$ and $s_1=s^*_1$ and $t=t^*$, so the algorithm will correctly find a solution.

We see that in either case, if a solution exists, the algorithm will successfully output a valid solution; and those are the only two cases that can occur if a solution exists.
Conversely, if no valid solution exists, it is easy to see that the algorithm will correctly output that no cut exists.


Data Structure for Representing a Math Expression I'm looking to improve my object-oriented design skills and I came across a problem which asked to design classes to represent a mathematical expression such as (a + b) * ( c - d / e) in memory so that it could be evaluated (by adding an evaluate method if need be in the class some time later)

The simplest solution I came up with was to store this expression in a stack (push(a), push(+), push(b)....), or may be even in an array (arr[0] = a, arr[1] = +...)

I feel like this is bad design and I read online that a binary tree (expression tree) is better to represent such an expression, but I am not sure why it is better.

Can someone help me understand this? Does the binary expression tree provide some benefits over storing in a stack?

Different representations are useful for different purposes. Think what kinds of things you might want to do with the expression, and think how each of them would be done using the stack representation and using the binary tree representation, and choose for yourself.

For fun, you may also want to consider something completely different, e.g. the english language representation: e.g. "the product of the sum of a and b, and the difference between c and d over e", or the representation as X86 machine code which would compute this expression, etc.

Things you may want to do with an expression (in any particular program you would probably need only a small subset of these):

Evaluate it, given certain values of the variables

Just once
Evaluate the same expression repeatedly for different values, with very high performance requirements

Perform simple algebraic manipulation, e.g. simplifications such as replacing x - x => 0, x*1 => x, etc.
Perform sophisticated algebraic manipulation on it, e.g. factorize the polynomials, compute derivatives or integrals.
Understand the expression stored in a variable when you're debugging the program
Format it as a string for displaying to the user
Render it as a mathematical expression to MathML
Draw it as a mathematical expression on a Javascript canvas
Compare two expressions for equivalence
Compare two expressions for equivalence ignoring variable names, e.g. a * a + b being equivalent to p * p + q
Convert a user-supplied string into an expression, checking it for well-formedness
...

Honestly speaking, I can find only one item of these for which the stack representation can possibly make things easier than the binary tree representation, and the array representation seems just completely useless.


Variation of Set Cover Problem: Finding a maximum-sized collection of disjoint set-covers I have the following problem, which seems to be similar to Set Cover.

We are given a set $U$ of elements (the universe, e.g., $U=\{1,2,3,4,5\}$).
We're also given a set $S$ of subsets (e.g., $S=\{\{1\},\{2\},\{3\},\{4\},\{5\},\{1,2,5\},\{1,3,4\},\{2,3,4,5\}\}$).

The standard set cover problem asks for the minimum subset of $S$ that covers the whole universe $U$, i.e., the smallest set-cover.  In our case this would be $\{\{1\},\{2,3,4,5\}\}$.

However, I'm interested in finding a collection of set-covers where each subset from $S$ is used at most once.  I want to find the largest such collection possible, i.e., to find as many different, disjoint set-covers of $U$ as possible.  Considering our example, the three set-covers $\{\{1\},\{2,3,4,5\}\}$ and $\{\{3\},\{4\},\{1,2,5\}\}$ and $\{\{2\},\{5\},\{1,3,4\}\}$ would be the output, since each one is a set-cover of $U$ and they are pairwise disjoint (no subset from $S$ is used in more than one set-cover).

Just testing all possible combinations of set-covers is definitely not an option. I have tried using an algorithm for set cover (ILP implementation) repeatedly, eliminating all used subsets in between runs. However, I'm certain that this strategy does not actually maximize the number of all possible covers.

Edit 1: I will try to describe the size of my problem a bit better. The typical size of $U$ is about 4000. $S$ consists of about 50 subsets. Each element of $S$ covers on average about 70% of $U$. Please keep in mind that I don't want to find all subset combinations out of $S$ that cover $U$. I just want to determine the maximum number of set covers using each subset from $S$ only once (or not at all). As of now I'm guessing the maximum number of possible covers is approximately 5.

The desired output from your algorithm might be exponentially large.  (There could be exponentially many set covers).  Therefore, you can't possibly expect to have an efficient algorithm in general.

One approach could be to code this up as a SAT (or ILP) problem, and add blocking clauses, so that in each iteration it gives you a new set cover that you haven't seen before.  Whether this will be effective in practice will depend upon many factors, such as how many set covers exist.

To help us help you, I suggest you tell us more about the parameters and structure of your particular problem.  What would be a typical size of $|U|$ and of $|S|$?  What would be a typical number for the total number of set covers (the size of the output that you're hoping to produce)?  Is there any structure in $S$ that might be helpful?  The best algorithm for your particular situation is likely to depend upon these factors.

Edit: Thank you for the additional details!  That helped.  So, it sounds like your goal could be described: given $k$, test whether there exist $k$ disjoint set covers from $S$ (i.e., test whether there exists $C_1,C_2,\dots,C_k$ where $C_i \subseteq S$, $C_i$ is a set cover, and $C_i \cap C_j = \emptyset$ for all $i,j$).  This is the decision problem version of your problem; if we can solve the decision problem, then we can use binary search on $k$ to find the maximum number you're looking for.

Given your problem size, the first thing I'd try would be using a SAT solver.  Here's how you could formulate your problem in a way that would let you apply an off-the-shelf SAT solver.  Suppose $S=\{s_1,s_2,\dots,s_{50}\}$, where each $s_i$ is a subset of the universe $U$.  Introduce boolean variables $x_{i,j}$ (where $1 \le i \le 50$ and $1 \le j \le k$), with the intent that if $x_{i,j}$ is true, then the $j$-th cover $C_j$ will include $s_i$ (in other words, the $j$-th cover contains the subsets $\{s_i : x_{i,j} \text{ is true}\}$).  We obtain the following constraints, which can each be expresses as CNF clauses:

For each $i$, at most one of $x_{i,1},x_{i,2},\dots,x_{i,k}$ is true.  One way to express this is as the conjunction of clauses $(\neg x_{i,j_1} \lor \neg x_{i,j_2})$ over all $j_1 \ne j_2$, i.e.,

$$\bigwedge_{1 \le j_1 < j_2 \le k} (\neg x_{i,j_1} \lor \neg x_{i,j_2}).$$

(Other ways of encoding this constraint are described here.)  This expresses the constraint that the $k$ set-covers are disjoint.
For each $j$, $\{s_i : x_{i,j} \text{ is true}\}$ is a set cover.  In other words, for each $j$ and each $u \in U$, there exists $i$ such that $u \in s_i$ and $x_{i,j}$ is true.  This can be expressed as the following conjunction of clauses:

$$\bigwedge_{j,u} \bigvee_{i : u \in s_i} x_{i,j}.$$
Optionally, you could break the symmetry here by imposing a lexicographic order on the set-covers.  For instance, you could require that when $1 \le j_1 < j_2 \le k$, then $(x_{1,j_1},x_{2,j_1},\dots,x_{50,j_1}) < (x_{1,j_2},x_{2,j_2},\dots,x_{50,j_2})$ (using the lexicographic ordering on bit-strings of length 50).

You could then try using an off-the-shelf SAT solver and see if it is able to complete on this problem in a reasonable amount of time.


Distinct Minimum Weight Spanning Trees I am trying to find the total number of distinct minimum weight spanning trees(MWST) in a simple, undirected, unlabeled and weighted graph but I am confused whether should I have to consider Isomorphic trees(if it is present) as a single minimum weight spanning tree or not while counting the distinct MWSTs because graph is unlabeled.

For example, If I have a graph as :

Now, I have to find the Total number of distinct minimum weight spanning trees(MWST) in the above weighted graph.

I got total $3\times2 =6 $ possibilities of MWSTs but I also found the possibility of Isomorphic trees in these total $6$ MWSTs because graph is unlabeled. For example,the below $2$ MWSTs are Isomorphic in nature for the above given graph.

Similarly , If I have a simple, weighted, undirected and unlabeled graph as :

Now, I got total $2^{2} \times 2^{4} = 64$ MWSTs but If I consider Isomorphism property in a graph then I am getting 2 Isomorphic Trees as :

So, If I consider the possibility of many Isomorphic trees like above in the given graph then total number of distinct MWSTs will be less than $6$ and $64$ in the above 2 cases respectively. But I am not sure whether it is correct or not.

So, My doubt is :- While counting the total number of distinct MWSTs in an unlabeled weighted graph, Should I have to consider Isomorphic MWSTs as a single minimum weight spanning tree  or not ?

There could be a few reasonable answers.

The simplest answer is that there are 6 minimum weight spanning trees (MSTs) in the first case and 64 MSTs in the second case. Look, the fact that you have said the same numbers and I can understand you perfectly means that interpretation makes some sense. Indeed, a strict definition/procedure can be given to yield those two numbers, although I will not be doing that here.

Let me proceed with another natural and interesting approach according to the conditions. How can we count distinct distinct MSTs of a given unlabelled weighted graph $G$? Here is one reasonable procedure. Initially we have counted 0 MST. Now someone will present to us the MSTs one at a time together with $G$ to us. Every information that is available should be presented to us accurately, including whether two vertices are connected and what is the weight of each edge and which edge is selected as part of the current MST. How these information will be presented can be arbitrary. Vertices can be labelled arbitrarily. The order of edges presented can be arbitrary. If drawn graphically, the shape of each edge and the location of the each vertex can be arbitrary. Etc. Whenever we can be confident that we are seeing a new MST, we will increase the count by 1. Using this approach, which is probably what you meant by considering "isomorphic MWSTs as a single minimum weight spanning tree", we will count 3 MSTs for the first graph and 20 MSTs for the second graph.

In practice, the second approach is too difficult for us to come up with results that we can understand or that could be beautiful. So, while I like the second approach very much as a challenge, I would suggest that you go with the first approach in a casual setting.

Note that there are a few ambiguities inherent in the question that needs to be defined formally (a.k.a. rigorously) before we can agree what is the way to count. For example, what does it mean by an "unlabelled weighted tree"? Do we require that the same weight be assigned to all edges that could be mapped to each other under an graph isomorphism (which happens to be the cases here)? How will we distinguish two "unlabelled weighted" trees? These questions should have been answered before we can count the number of distinct MSTs in a definitive way.


splitting of people betwen groups with group prioritiy list per person Looking for an algorithm for splitting a list of people (S) into groups (G), |S| <= |G|, more than one person wants to be in a certain group.
Every person has a monotone ranking from highest (most desired) to lowest of all the groups.
Using this list I want to find the "best matching".
"best matching" is when you maximize the "score of the matching".
"score of the matching" is the sum of the group rankings of the people that got matched with the group, i.e. summing the ranking that the people gave to the group which was chosen for them.
I'm also interested in ideas for other "fairness" values for maximization.

If you want to maximize the sum of the scores for each participant, this is an instance of the assignment problem; use the Hungarian algorithm, or any other algorithm for computing a maximum matching.
You might also be interested in stable marriage algorithms, which have a different notion of fairness.


What happens when an internet connection is faster than the storage write speed? If one attempted to download a file at a speed of 800 Mb/s (100 MB/s) onto a hard drive with a write speed of 500 Mb/s (62.5 MB/s), what would happen? Would the system cap the download speed?

Many protocols, including TCP which is most widely used protocol on the Internet, use something called flow control. Flow control simply means that TCP will ensure that a sender is not overwhelming a receiver by sending packets faster than it can empty its buffer. The idea is that a node receiving data will send some kind of feedback to the node sending the data to let it know about its current condition. So, two way feedback allows both machine to optimally use their resources and prevent any problems due to mismatch in their hardware.

https://en.wikipedia.org/wiki/Flow_control_(data)


Binary tree algorithm asymptotic analysis problem Assume we have a perfectly balanced Binary tree.
We have the following algorithm: For each passed node, traverse through all its ancestors and then do the same algorithm for the left and right child of the node.

So, the way I try to find the Big-O complexity is this: There are O(N) nodes in the tree and each has O(log2N) ancestors, so overall we'll have O(N*log2N) complexity if we start the algorithm from the root.

Now consider another problem for the same Binary tree: For each node, go to its left and right child. If the node doesn't have any children, for each ancestor, go through all the previous ancestors.

Now my attempt for finding the complexity: We basically keep going through every node until we reach the leafs. There are N/2 leafs in a perfect Binary tree with N nodes and for each leaf we have (log2N) ancestors. Since for each ancestor we have to traverse every previous, the overal compexity when we're on a leaf is O(Log2(N)^2), so overall complexity becomes O(N*log2(N)^2).

The problem is that I think the algorithms basically do the same thing. Why do I get different complexities for them?

They're not the same thing.  Consider some node $x$.  Ask yourself how many times the algorithm does the operation "iterate through all the ancestors of $x$".

The first algorithm does this operation once.  The second algorithm does this operation $k$ times, where $k$ is the number of descendants of $x$.  So, it's no surprise that the second algorithm takes longer: it's doing a lot more repeated work.


What the heck is a memory channel "CS bus"? While I was reading about memory architecture from the CMSC 22200's Lecture 17 of University of Chicago, I got stuck on determining the meaning of the word "CS" used for describing a bus as part of memory channel:

However I didn't find any additional source pointing out that bus. And furthermore, I found on different reference that:

  The memory channel is made up of a data bus and an address/comm and
  bus.

So, I don't know from where they got the information about the "CS bus"? And what is it exactly?

I think it is the "Chip Select" part which is mentioned at slide 26.

It probably selects whether to use the chip on the front or in the back.


Proof of decidability of determining whether a DFA accepts a string I want to ask the acceptance problem:
Whether a particular deterministic finite automaton accepts a given string can be expressed as a language, $A_{DFA}$.
Show $A_{DFA}$ is decidable.
The proof in the textbook (Siper page 195) uses two steps:

$M$ = “On input $\langle B,w\rangle$, where $B$ is a DFA and $w$ is a string:

Simulate $B$ on input $w$.
If the simulation ends in an accept state, accept. If it ends in a
nonaccepting state, reject .”

What exactly is the meaning of "simulating $B$" in the first step? In my understanding, if $M$ wants simulates multiple DFA $B$, the parameters of $M$ (transition function or acceptance state) need to be changed according to the different input DFA $B$ and input string $w$, since different DFAs may have different structure. In other words, can a TM simulate infinite DFAs? And how it can be done? I know this question may be trivial, but it really bugs me. Any clarification will be appreciated.

I've often found that, with problems like these, it's easiest to reason by analogy to software, since anything you can do with a computer you can do with a TM and vice versa (with a giant asterisk). The problem $A_{DFA}$ essentially is the following: given a DFA $D$ and a string $w$, determine whether $D$ accepts $w$. In software, you could imagine that you'd want to write a method

bool accepts(DFA D, string w)

that takes as input a DFA $D$ and a string $w$, then returns the answer. Notice that we're given the DFA as a parameter, since if we don't have it, then there's no way that we can answer the question. It would be like someone saying "I'm hiding a DFA behind my back - can you guess whether it accepts a given string?"

The pseudocode for this function might look something like this:

bool accepts(DFA D, string w) {
    currState = D.startState;
    for (char ch: w) {
        currState = D.transitionTable[currState][ch];
    }
    return D.isAcceptingState(currState);
}

Since this is something that we can do with a computer, it's certainly something that we can do with a TM.

Given this code, it's probably clearer what the TM you described above would do. It doesn't take in infinitely many DFAs or strings - it just takes in a single DFA and a single string at a time. There are infinitely many possible choices for what that DFA could look like or what that string could be, but at any one point in time the TM works on just a single string and a single DFA. The fact that the TM (or this code) correctly works on every possible DFA and every possible string is why $A_{DFA}$ is decidable: there's a TM that, given an arbitrary string, decides whether it's in the language.


Find a graph for which Kruskal's algorithm achieves worst-case running time I am working on a problem in which I must find a graph with edge weights on n vertices, for which Kruskal's algorithm achieves worst-case running time.  I am using a UNION-FIND data structure, but with no optimisations (path compression or weight/height union rules).

The version of Kruskal's which I am using is as follows:

Kruskal(G)
  for each vertex  ∈  do MAKE−SET()
  sort all edges in non-decreasing order
  for edge ,  ∈  (in the non-decreasing order) do
    if FIND  ≠ FIND() then
      colour (, ) blue
      UNION(, )
  od
  return the tree formed by blue edges

Also, MAKE-SET(x), UNION(x, y) and FIND(x) are defined as follows:

MAKE-SET()
  Create a new tree rooted at
  PARENT()=x

UNION(, )
  PARENT FIND() ≔ ()

FIND()
   ≔
  while  ≠ PARENT() do
     ≔ PARENT()
  return y

After having looked at this post, my idea was to construct a graph on n vertices, such that there are as many redundant edges as possible and at least one necessary edge which is checked last (this edge must have the greatest weight).

I've looked at the specific cases n = 4 and n = 5 and have tried to construct such graphs in these cases.  However, I am struggling to generalise to arbitrary n.

I would appreciate any hints for progressing with this problem.  Thank you.

Let the answer be a complete graph $G = (V,E)$ with $|V| = n$ and a weight function $W : E \to \mathbb{R}$

Let the vertices be denoted by $1,2,\dots n$ and edges between $i$ and $j$ as $(i,j)$.

Now define the weights of all the edges as follows:
$$W(i,j) = j-1, \forall \ 1 \le i < j$$

(Assuming you break ties for the edges on the basis of the value of the nodes $i,j$)

If you add a break statement once all $n$ nodes have been merged, then the algorithm will iterate on all the $\binom{n}{2}$ edges (except the last $n-1$) before finishing execution. This is because it will iterate all the edges in non decreasing order and it will find that except for the edge $(1,j)$ all other edges connect nodes belonging to the same disjoint set.

The running time will thus be $\mathcal{O}(\alpha(n + \binom{n}{2}))$


Return the subset with smallest cardinality of an array whose elements sum to at least a given value Suppose we are given an array $A[1\ldots n]$ and a value $C$.

Is there an algorithm with linear expected runtime that can produce an array that is the subset  with smallest cardinality of $A[1\ldots n]$ whose elements sum to at least $C$?

First, we randomly select an element that is not the smallest one as a pivot, and partition the elements into two subsets: the ones less than the pivot ($P$) and the ones no less than the pivot ($Q$). Let $S$ be the sum of elements in $Q$.

If $S=C$, then $Q$ is exactly the optimal subset we want.
If $S<C$, then the optimal subset is the union of $Q$ and the subset with smallest cardinality of $P$ whose elements sum to at least $C-S$, which can be found by recursively applying this algorithm on $P$.
If $S>C$, then the optimal subset is the subset with smallest cardinality of $Q$ whose elements sum to at least $C$, which can be found by recursively applying this algorithm on $Q$.

Let $T(n)$ denote the expected running time of this algorithm on an input of $n$ elements, we have
$$T(n)\le \frac{1}{n-1}\sum_{i=1}^{n-1} T(\max\{i,n-i\})+cn,$$
where $c$ is a constant. By mathematical induction we can conclude that $T(n)\le 4cn$, thus the algorithm runs in expected linear time.

You can also use the idea of median-of-medians to get a worst-case linear time algorithm by selecting the pivot as the apporximate median produced by the median-of-medians algorithm.


Lower bound on $c_n = 4c_{\lfloor n/2 \rfloor} + n$ Define a sequence $c_1,c_2,\dots$ by the equations
$$ c_1=0, \quad c_n = 4c_{\lfloor n/2 \rfloor} + n \text{ for all } n > 1. $$
Prove that $\frac{(n+1)^2}{8} < c_n$ for all $n \geq 2$.
Hint: $\lfloor \frac{n}{2} \rfloor \geq \frac{n-1}{2}$ for all $n$.

How do I solve this question? I have no idea how to start.

Let's start with the case $n = 2^k$. We have
\begin{align}
c_{2^k} &= 2^k + 4c_{2^{k-1}} \\ &= 2^k + 4 \cdot 2^{k-1} + 16c_{2^{k-2}} \\ &= \cdots \\ &= 2^k + 4 \cdot 2^{k-1} + 4^2 \cdot 2^{k-2} + \cdots + 4^{k-1} \cdot 2^1 + 4^k c_1 \\ &= 2^k + 4 \cdot 2^{k-1} + 4^2 \cdot 2^{k-2} + \cdots + 4^{k-1} \cdot 2 = \\ &= 2^k(1 + 2 + 2^2 + \cdots + 2^{k-1}) \\ &= 2^k(2^k-1).
\end{align}
It is easy to prove by induction that the sequence $c_n$ is monotone. Therefore, if $2^k \leq n < 2^{k+1}$,
$$
c_n \geq c_{2^k} = 2^k(2^k-1) > \frac{n}{2}\left(\frac{n}{2}-1\right).
$$
Now
$$
\frac{n}{2}\left(\frac{n}{2}-1\right) \geq \frac{(n+1)^2}{8} \Longleftrightarrow
2n(n-2) \geq (n+1)^2 \Longleftrightarrow n^2 \geq 6n + 1.
$$
This holds for all $n \geq 7$. You can check that your inequality holds for $n=2,3,4,5,6$ directly.

You can also likely prove the inequality directly by induction, but the argument above is more similar to stuff you might actually see later on. The idea is that we find a specific type of $n$ for which $c_n$ is particular easy to calculate and to compare to $n$, and then we try to understand $c_n$ for all $n$ using these specific values.


Detecting face like patterns using CNN based face detector I have a CNN based object detector trained on WIDER Face dataset. It can successfully detect human faces in a given image.

Now, I am trying to detect abstract face and minimalistic face patterns in clouds or houses etc but having no success.

Initially, I thought I could lower the detection threshold to detect such patterns, but such scheme didn't work.

My question is there any way other than collecting and labelling such training examples (face like patterns) to solve this problem.

You probably need a training set that contains examples of abstract faces and minimalistic face patterns.  There's no reason to expect a neural network trained on real faces to detect abstract face patterns; neural networks don't necessarily generalize that way.


Does Deadlock imply Starvation If there is a deadlock between the processes does that mean that there is starvation also?

My Thinking:
deadlock is no process using that resources , but starvation is like not giving chance to only that process so there is progress in starvation but not in deadlock
Is my thinking right?

You should first state the deadlock freedom property and the starvation freedom property more precisely.
I use the definition in the Book: The Art of Multiprocessor Programming; Section 2.2.

Freedom from Deadlock If some thread attempts to acquire the lock, then some thread (not necessarily the thread referred to in the if statement; emphasis added) will succeed in acquiring the lock.
Freedom from Starvation Every thread that attempts to acquire the lock eventually succeeds.

Note that by definition, starvation freedom implies deadlock freedom. Thus, if a mutual exclusion algorithm suffers from deadlock, it also suffers from starvation.
A direct argument is that: deadlock means that some thread attempts to acquire the lock, but no threads succeed. That is a special kind of starvation.


How do you prove that two languages are equivalent? How can you show that the Language accepted by an NFA and the reverse NFA is the same?

For a language $L$, there is an $L^R=\{ w^R \mid w \in L\}$

Let's say that $w^R$ is the string obtained by reversing the string $w$.

I know that it involves using induction on the length of the input, but I would really appreciate some help.

There's an algorithm for this. Construct a DFA from you NFA, construct the reverse DFA, and check whether the two DFAs accept the same language (for example, you could construct the DFA for the symmetric difference and see if it accepts anything). If you want a more serious answer, you'll need to tell us more about your $L$.


Prove that the equal-length concatenation of regular languages is context free If A and B are regular, then prove that $A@B = \{xy \mid x \in A \text{ and } y \in B \text{ and } |x|=|y|\}$ is always context free.

So I'm trying to come up with the proof that looks something like this. Knowing that $A$ and $B$ are regular, we can conclude that there exists NFA for $A$ and $B$ respectively. Then, we can work out these NFA into two separate PDA: one PDA that would accept $x$ from $A$ and another PDA that would accept $y$ from $B$. Then we need to somehow merge two PDAs into one modifying it so that it controls the length of $x$ and $y$ too and accepts only in the case when $x=y$.

I am just trying to come up with the set of legitimate steps that would follow through this, and that these steps would always work so that given $A$ and $B$ are regular final the PDA will always accept $A@B$.

To expand a bit on @babou's comment, let $M_A$ and $M_B$ be the FAs for $A, B$ respectively. Make a PDA that acts like this:

(1) repeat
      read the input, using MAs transition rules.
      For each character read, push a marker on the stack.
    until MA enters a final state or no input remains
(2) if no input remains and MA is in a final state, go to (3)
    else if no input remains and MA is in a non-final state, halt and reject
    else nondeterministically go to (1) and (3) [guessing that we're done with the first half]
(3) repeat
      run the PDA on any remaining input, using MBs transition rules
      For each character read, pop the stack
    until the stack is empty or no input remains
(4) if MB is in an accept state, no input remains, and the stack is empty, halt and accept
    else halt and reject

(I apologize in advance for any missing details/programming errors, but the intent, I hope, is clear: process the first part of the input, guess that we're in the middle and process the second part.)


Full adder carry expression I'm learning about logic circuits and I've come across full adder. In the book they  derived its two carry out expressions -

Cout = x&&y || x&&z || y&&z
and
Cout = x&&y || (x'&&y || x&&y')&&z

I've tried to get the second equation from the first one but couldn't. Any one knows how to do that?

From your question it is unclear what $x$, $y$ and $z$ are. However, the two formulas are equivalent. Let me use products to denote a logical "AND" and additions to denote a logical "OR" so that your first formula becomes $xy + xz  + yz$

If you gather $z$ in the last two terms you get:
$xy + (x+y)z$.

Notice how the second term $(x+y)z$ is true iff $z$ is true, and at least one of $x$ and $y$ is true. However, if both $x$ and $y$ are true, the whole formula is true regardless of the truth value of the second term (since the first term is $xy$).
You can then replace $(x+y)$ with $(x \oplus x)$ (where "$\oplus$" denotes the exclusive OR) to obtain:
$xy + (x \oplus y)z$ or, equivalently, $xy + (x'y + xy')z$.


Relation between Hoare Type Theory and pointers My understanding is that in Hoare Type Theory every imperative statement has a type of the form {Pre}res:T{Post} where T is the type of the result of the computation and Pre and Post are propositions representing respectively the pre and postconditions of the statement and res is the result of type T which can appear in the postcondition.

Given the following program in pseudo-C:

int i=0;
int*p=&i;
*p=1
return i;

How can Hoare type theory represent the the fact that i must be 1?After all,it's not clear i is modified in the above snippet,and it can be hidden even from the programmer if we begin to add lambdas and partial application

A pointer to a variable creates an alias. When the alias is modified, the corresponding variable is modified as well. Therefore, the rule for an assignment in Hoare's logic is not just update the value, but update the value for all associated aliases. Let's apply it to the example:

{True}        int i=0;  {i = 0}
{i = 0}       int*p=&i; {i = 0; [*p, i]}  /* *p and i are now aliases */
                                          /* The postcondition can be written as: */
                        {[*p, i] = 0}     /* In particular, *p = 0 */
{[*p, i] = 0} *p=1;     {[*p, i] = 1}     /* In particular, i = 1 */
{[*p, i] = 1} return i; {i = 1}

The general rules to reason about programs with pointers are given by Separation logic. The information whether two expressions reference the same memory location is obtained by pointer analysis and alias analysis.


requirement for pumping lemma in regular language I am a bit confused on the theory of the pumping lemma. As I know is used to decide if a language is regular or not.

This is what I have understood so far though For a regular language $L$, there exists a $p > 0$ such that for all $w ∈ L$ where $|w| ≥ p$, there exists some split $w = vxu$, for which the following holds:

$|vx| ≤ p$

$|x| > 0$

$vx^iu ∈ L$ for all $i ≥ 0$

but what is the rationale behind the requirement of $|vx| ≤ p$ what happens if we drop that requirement??

thanks ahead

$|vx| < p$ mean that $x$ is short and it is at the beginning of $w$. If you were to remove that constraint, all regular languages would still satisfy the lemma, but more irregular ones would too. For example $L = \{a^n \mid n ~\text {is not prime}\}$, when $n = m \cdot k $ can be pumped by taking $x = a^k$.


Blind sorting an array with a singular sort function? I am doing some interview prep, and I came across a question that really stumped me, and it didn't provide an answer.

The premise of the question was as follows:

You are given some unsorted array A of size n. You are not allowed to access the array, read values, or compare the values.

The only manner in which you may interact with said array is with a BlockSort() functions, such that calling BlockSort(index) will automatically sort the elements within the inclusive bounds of [i,i+u] for some arbitrary but fixed u, such that u≥1.

Sort A with O((n/u)^2) calls to BlockSort.

My initial approach to this question was to mimic Bubble Sort, except stagger the calls to BlockSort, such that each successive call overlaps with one element of the previous call, (i.e. BlockSort(0,u), BlockSort(u,2u)...etc.) and then after iterating like that through the array once, you are left with the global maximum at the end of the array, and an unsorted array of size n-1, and then you can recursively solve the problem.

This has a time complexity of O((n^2)/u) though.

I have thrown an hour or 2 at the problem, and I can't quite see how they achieved O((n/u)^2).

Is there anything I could think about to get to the answer?

Your approach by mimicking Bubble Sort is pretty good.

Here is a hint. Since we can sort a block, we can raise half a block of the largest elements so far like a bubble each time. For example, when $u=5$, if we have done BlockSort on [0,5], [3,8] and [6,11] successively, we will have placed the largest 6/2=3 elements among the first 12 elements at index 9,10 and 11, the end of subarray so far.


Proving that picking odd-numbered symbols can create the universal set from a non-regular language Let's define the following operations:

$odd(string) = $ odd characters of $string$, $even(string) = $ even characters of $string$

Now say we have some language $L$, we will then define the following languages:

$odd(L) = \{odd(w): w \in L\}$, $even(L) = \{even(w): w \in L\}$

Need to prove that there exists a non-regular language, $L_N$, such that $odd(L_N)$ and $even(L_N)$ are both regular languages.

I thought of a few examples that might produce obvious regular languages with $odd$ and $even$, one of which was the language:

$L_1 = \{w \in \{a,b\}^*: |a|_w = |b|_w\}$, where $|x|_w =$ # of $x$'s in the string $w$

I know how to prove that this is non-regular, and upon inspection of a lot of values of $odd(L_1)$ and $even(L_1)$, it appears both produce the language $\{a,b\}^*$ which is obviously a regular language. Don't really know how I could prove that equality though.

You want to show that $\operatorname{odd}(L_1) = \{a,b\}^*$. This is a set equality claim, and you show it the way you can approach any such claim:

Show $\operatorname{odd}(L_1) \subseteq \{a,b\}^*$.

That's trivial.
Show $\operatorname{odd}(L_1) \supseteq \{a,b\}^*$.

Let $w \in \{a,b\}^*$. Can you construct $w' \in L_1$ so that $w = \operatorname{odd}(w')$?

   You only need to fix symbol counts, so brute force works:
 $w' = w_1 \overline{w_1}  \cdots w_n \overline{w_n}$ with
 $\overline{x}$ the "inverse", i.e. it maps $a$ to $b$ and vice versa.

Thus, $w \in \operatorname{odd}(L_1)$. Since $w$ was chosen arbitrarily,
the claim follows.

A similar proof works for $\operatorname{even}(L_1)$.


Using Dijkstra to find shortest path in relation to two weight functions? I'm given a graph and two weight functions, $w_1$ and $w_2$, such that there doesn't exist a negative loop in the graph in $w_1$ and $w_2$. I'm also given two vertices, $s$ and $t$, and am asked to find the lightest path from $s$ to $t$ in relation to $w_1$, out of all the lightest paths from $s$ to $t$ in relation to $w_2$.

I get that this question begs for me to modify Dijkstra somehow, but I just can't seem to find the intuition to do so. Any guidance would be appreciated!

Let $\epsilon>0$ be an infinitesimal. Define a new weight function $w(v) = w_2(v) + \epsilon w_1(v)$, and run Dijkstra with respect to this weight function.

How do you implement infinitesimals? There are two options. The first is to let $\epsilon$ be a small enough number. For example, if $W_1$ is the maximal $w_1$-weight and there are $n$ nodes, then $\epsilon < 1/(nW_1)$ should be small enough (why?). The other option is to notice that you only have to be able to compare numbers of the form $w_2 + \epsilon w_1$. We have $x_2 + \epsilon x_1 \leq y_2 + \epsilon y_1$ if either $x_2 < y_2$ or $x_2 = y_2$ and $x_1 \leq y_1$. Using this comparison oracle, you can implement infinitesimals in earnest.


Is IEEE 754 float arithmetic associative, commutative, distributive, etc? Why? Does the associative/commutative/distributive/etc property hold for arithmetic performed with IEEE 754 floats?

Obviously the answer is no to most of those questions, but do any of the properties of standard arithmetic hold? How can one formulate proofs (or at least proof-like statements) explaining why any particular property does or does not hold?

The IEEE 754 standard defines exactly how floating-point arithmetic is performed. For many interesting theorems, you will need to examine the exact definition. For some less interesting ones, like a+b = b+a or ab = ba, all you need to know that IEEE 754 always calculates the exact result, rounded in a deterministic way. For non-theorems, like (a+b)+c = a+(b+c), which is false, all you need is a counterexample which is usually easy to find.


What is the point of the "respect" requirement in cut property of minimum spanning tree? The cut property stated in terms of Theorem 23.1 in Section 23.1 of CLRS (2nd edition) is as follows.

  Theorem 23.1 Let $G = (V, E)$ be a connected, undirected graph with a real-valued weight function $w$ defined on $E$. Let $A$ be a subset of $E$ that is included in some minimum spanning tree for $G$, let $(S, V-S)$ be any cut of $G$ that respect $A$ (emphasis added), and let $(u,v)$ be a light edge crossing $(S,V-S)$. Then, edge $(u,v)$ is safe for $A$.

Why does this theorem require that the cut $(S,V-S)$ respect $A$? How is this requirement used in the correctness proof? I do not see what would fail if the requirement was removed.

Some Definitions:

Cut: A cut $(S, V-S)$ of an undirected graph $G=(V,E)$ is a partition of $V$.
Cross: An edge $(u,v) \in E$ crosses the cut $(S,V-S)$ if one of its endpoints is in $S$ and the other is in $V-S$.
Respect: A cut respects a set $A$ of edges if no edge in $A$ crosses the cut.
Light edge: An edge is a light edge crossing a cut if its weight is the minimum of any edge crossing the cut.

I don't have the book handy. I assume that

"safe" means that $(u,v)$ can be added to $A$ and we get another subset of a minimal spanning tree of $G$, and
the goal is a correctness proof of Prim's algorithm¹.

Now, say the cut did not "respect" $A$. That means that there already is an edge in $A$ that crosses it. By choosing a second edge from that cut -- which may happen even with pairwise distinct weights! -- we may introduce a cycle and lose the tree property.

By requiring that the cut "respects" $A$ we know that $A \subseteq S$ and we can not introduce a cycle².

The assumptions of this theorem may be stronger than strictly necessary -- as long as we do not create a cycle, we do not per se need to care about other edges in the cut -- but we can build an algorithm around them, so the theorem is a convenient way to ensure its correctness.

Note how the theorem directly implies that fact since Prim's algorithm maintains such a cut and chooses light edges from it to grow the tree.
In the algorithm, we'll always have $A=S$.


Description for languages that can be solved in time(n)? How can one describe all languages that are in
$\mathrm{TIME}(n)$?

It can't be all the regular languages only, as for example $L = \{a^n b^nw \mid w \in \Sigma^* \land n \geq 1\}$ is not regular but in $\mathrm{TIME}(n)$. Furthermore there are regular languages (like any modulo languages) that are not in $\mathrm{TIME}(n)$.

So, is there a nice description for all $L \in \mathrm{TIME}(n)$?

We're not good at characterizing languages that can be decided in deterministic polynomial time. There are multiple characterizations of $\mathrm{NP}$ (e.g., nondeterministic Turing machines, polynomial witnesses, existential second-order logic), but $\mathrm{P}$ seems to be just "stuff you can do in polynomial time on a Turing machine."

Similarly, it's unlikely that there's any alternative characterization of linear time beyond its literal definition.

  Furthermore there are regular languages (like any modulo languages) that are not in $\mathrm{TIME}(n)$.

No there aren't. You can decide any regular language in linear time using a DFA (trivially modify its description so it's a Turing machine).


Is the set of TMs that does not reach most cells to the right computable? Let $L_{NTF} = \{ \langle M \rangle \mid $ for every $x\in\Sigma^* $ the machine $M$ does not reach the $|x|+10$'th cell during its calculation on $x$. $ \}$.

I would like to prove or disprove $L_{NTF} \in RE$.

I know how to easily prove that $L_{NTF} \in Co$-$RE$, because it is enough to find one word $x$ such that $M$ will reach the $|x|+10$'th cell during its calculation on $x$. There is a finite number of configurations as long as the machine does not reach the $|x|+10$'th cell, so if I see a configuration is repeated I can deduce that the calculation will not end, but since I want it not to reach the $|x|+10$'th cell it is fine by me. That is to say, for a given input $x$ I can decide whether or not it reaches the $|x|+10$'th cell during $M$'s calculation on $x$.

So this tells me that $\overline{L_{NTF}}\in RE$, that is $L_{NTF}\in Co$-$RE$.

But this idea will not assist me in proving $L_{NTF}\in RE$ because I may accept a TM $\langle M\rangle$ only after I will iterate over all possible $x\in \Sigma^* $, and since $\Sigma^*$ is $\aleph_0$ I will never accept a TM $\langle M\rangle$. This is my intuition for why $L_{NTF} \notin RE$.

So for proving this I have 2 options:

Showing a reduction $L\leq L_{NTF}$ where $L\notin RE$. I've tried using $\overline{L_{acc}}, L_d$ and $L_{\Sigma^*}$, but could not find such a reduction that will hold. I'm not sure which language should i reduce from?
Finding a correspoinding property using Rice's theorem. I believe this idea will not work because the property is on the TM and not on the language.
An idea similiar to (1), just showing a reduction $L\leq L_{NTF}$ where $L\notin R$. This will also be sufficient because it will prove me that $L_{NTF}\notin R$, and since I know $L_{NTF}\in Co$-$RE$ having $L_{NTF}\in RE$ will lead to a contradiction, thus we can deduce $L_{NTF}\notin RE$.

I believe it is either by option (1) or by option (3), but I could not find a reduction that will prove this...

Given a Turing Machine $M$ you can effectively construct $M'$ that does the following:

Given $x$, $M'$ overwrites $x$ with $\langle M\rangle$ up to length $|x|$ or end of $\langle M\rangle$, whichever comes first. Writes blanks on the rest of $x$, and puts an end marker on cell $|x|+1$.
$M'$ returns to the beginning of input and simulates $M$.
If $M$ accesses end marker at any point, $M'$ enters an infinite loop without moving any further to the right.
If $M$ accepts, $M'$ goes infinitely to the right.

Note this $M'$ has the following properties:

If $M$ halts on $\langle M\rangle$ then $M'$ will access $|x| + 10$th cell for some large enough $x$.
If $M$ does not halt on $\langle M\rangle$ then $M'$ will never access $|x|+10$th cell.


dynamic pseudo-code for simplified coin changing algorithm As a homework exercise our professor presented to us a simplified version of the coin-changing problem in which we do not need to minimize the number of coins used or track the number of possible combinations.  Instead we need only to determine if a certain subset of coins of same or varying denomination, equal exactly to, some amount M.

My recursion equation of the problem is as follows:

let k = 0

If ∑ (v1 + v2 + … + vn) = M
    return true

If ∑ (v1 + v2 + … + vn) < M
    return false

Else
    Increment k by 1
    make recursive call on coin subset {v1, v2, … v(n-k)}

The next question is to convert this into pseudo-code that represents a dynamic programming solution to this problem.

I'm a bit stuck.  If you were to make a table of every possible sum {v1 + v2},  {v1 + v2 + v3},  {v1 + v2 + v3 + v4}, etc. You could eventually find a solution but wouldn't that be a much less efficient brute force approach?

I assume the solution would include some implementation of memoization or some way to store and retrieve sums already encountered, but being that the problem is not an optimization problem, I'm having a hard time envisioning a dynamic solution.

Much of the dynamic programming examples that I see suggest iteratively subtracting elements, one item at a time, which is similar to the composition of my recursion equation but I don't see a modification that would make this pseudo code dynamic in nature.

If anyone could please enlighten me, I'd be very grateful

Given an integer $M>0$ and $n$ coins with integer values $v_1, v_2,\cdots, v_n$, where $M, n, v_i$ are positive, how can we determine if some of the coins can add up to $M$?

This problem is a common version of subset sum problem. There are many strategies to solve the problem.

Here is the pseudocode by dynamic programming that is about as simple as possible.

Let $s$ be an array of size $M+1$ with default value 0 and starting index 0. Let $s[0]=1$.
For $i$ from 1 to $n$, do:

For $j$ from 0 to $M$, do:

If $s[j]=1$, let $s[j+v_i]= 1$.

If $s[M]=1$, return yes. Otherwise, return no.

Here is an example to illustrate the algorithm. Let $M=7$. Coins are $1,3,3,5$.

$s=[1,0,0,0,0,0,0,0]$.
Here are $s$ at the end of each iteration.

$s=[1,1,0,0,0,0,0,0]$
$s=[1,1,0,1,1,0,0,0]$
$s=[1,1,0,1,1,0,1,1]$
$s=[1,1,0,1,1,5,1,1]$

return yes since $s[7]=1$

We can optimize the algorithm above in various ways.

We can stop the algorithm once we have found $s[M]=1$.
We can change $s$ to a double linked-list, whose elements are the realizable values in increasing order.
We can split the given array of values to two arrays of equal size or sizes with difference 1. Run the algorithm on each of two arrays. Check if we can select one number from each resulting array $s$ such that their sum is $M$, using two-pointer technique.
This last item means all other ways, as always.

Exercise. Adapt the algorithm so that it also tells the least number of coins used if the answer is yes.


Random Access Machines with only addition, multiplication, equality The literature is fairly clear that unit-cost RAMs with primitive multiplication are unreasonable, in that they

cannot be simulated by Turing machines in polynomial time
can solve PSPACE-complete problems in polynomial time

However, all of the references I can find on this topic (Simon 1974, Schonhage 1979) also involve boolean operations, integer division, etc.

Do there exist any results for the "reasonableness" of RAMs that only have addition, multiplication, and equality? In other words, which do not have boolean operations, truncated integer division, truncated subtraction, etc?

One would think that such RAMs are still quite "unreasonable." The main red flag is that they enable the generation of exponentially large integers in linear time, and due to the convolution-ish effects of multiplication, this can get particularly complex. However, I cannot actually find any results showing that this allows for any sort of "unreasonable" result (exponential speedup of Turing machine, unreasonable relationship to PSPACE, etc).

Does the literature have any results on this topic?

The other day I was reading a paper on parallelized random access machines without bit operations, which sounded very much like what you are describing. For these models NC is known not to equal P. See here: https://epubs.siam.org/doi/10.1137/S0097539794282930

The paper can also be found on Professor Mulmuley’s website.


graph theory analogue of rectangular matrix Graphs are usually defined as a set of vertices $V$ together with a set of edges $E$ consisting of elements $V \times V$. I'm interested in a slight generalization of this, where instead one has two sets $V$, $W$ and the edges are taken from $V \times W$. The adjacency matrix of such an object would be rectangular, as opposed to the adjacency matrix of a regular old graph, which is square. Is there a name for this?

I'm interested in this because I'm writing a data structure to represent a graph in terms of its partitioning into sub-graphs for the purposes of parallel computation. For example, given a graph $G$ on a vertex set $V$, we can partition $V$ into disjoint subsets $V_1$ and $V_2$; $G$ is then naturally divided into two subgraphs $G_1$ and $G_2$ describing connections among $V_1$ and $V_2$ respectively, and a "rectangular graph" $H$ describing connections between $V_1$ and $V_2$. I'd like to give the class a name that makes sense.

Such a graph is known as a bipartite graph.  There is a whole theory about bipartite graphs, including a number of algorithms that are specialized for bipartite graphs.


Category theory and graphs Could most categories , or a finite part of them be represented on a subset of a complete graph of N vertices (Kn) which is connected. and partly directed? Could all the axioms of category theory be written for such graphs?

A category consists of:

Objects.
Directed arrows between objects. There can be multiple arrows between any two given objects, or a unique arrow, or none.
A composition map for arrows that takes an arrow $f$ from $x$ to $y$ and another arrow $g$ from $y$ to $z$ and outputs an arrow $gf$ from $x$ to $z$.
Depending on the formulation, there might also be a distinguished arrow between every object and itself (the identity arrow).

The composition map has to satisfy the following axioms:

Associativity: if $f\colon x \to y$, $g\colon y \to z$ and $h\colon z \to w$ then $h(gf) = (hg)f$.
Identity: if $f\colon x \to y$ and $1_x\colon x \to x$ and $1_y\colon y \to y$ are the distinguished self loops then $f1_x = 1_yf = f$. (If the formulation does not include the distinguished self-loops: there exist arrows $1_x\colon x\to x$ and $1_y\colon y\to y$ such that $f1_x = 1_yf = f$.)

You can represent this data in many ways. A graph with multiple edges is, however, not enough, since you also need to specify the composition map.


Data Flow Analysis with exceptions Data flow analysis work over a control flow graph. When a language under consideration supports exceptions, control flow graph can explode.

What are the standard techniques for dealing with this blow-up?
Can we soundly disregard edges induced by exception? Data flow analyses anyhow compute over-approximations, so we would end up with a less precise but sound solution. Is this true?

Update: Here are few useful links that I was able to dig out at the end:

Analysis and Testing of Programs with Exception-Handling Constructs
Efficient And Precise Modeling of Exceptions for Analysis of Java Programs

Ignoring exceptions is unsound. Example:

let g = {
     raise E;
}
let f = {
     x := interesting_stuff();
     g();
     x := 0;
}

When analyzing f, you need to take into account the fact that g raises an exception, otherwise you would incorrectly conclude that x is always 0 on return from f.

I don't know that there is a “standard” technique for dealing with exceptions. There's some literature on the topic, I don't have any more idea of what papers are relevant than I can find by a Google search.

Formally, exceptions can be turned into conditional statements that propagate up the call chain, which of course blows up the control flow graph. In many concrete cases, the exception case is the less interesting case, where a lot of data gets killed, so it should be handled lazily in a forward approach (no need to analyze the liveness on the exception path if the handler kills the data).


Linear programing, objective function. variable depending on the sign of another variable I have the variable Si. How to express a variable Di in LP that satisfies:

Di=100*Si if Si>=0
Di=-200*Si if Si<0

The objective function would be Min{Sum(Di)}

I think it's cleaner to define two variables that represent the positive and negative parts of Si. Call them Si1 (= positive part) and Si2 (= negative part).

Si1 - Si2 = Si
Si1, Si2 >= 0

Probably you will also need constraints that say that if Si < 0 then Si1 must equal 0, and if Si > 0 then Si2 must equal 0. Introduce an additional binary variable y that equals 1 if Si > 0, equals 0 if Si < 0, and could equal either if Si = 0:

-M * (1 - y) <= Si
 M * y >= Si

where M is a large constant.
Then require Si1 = 0 if y = 0 and Si2 = 0 if y = 1:

Si1 <= M * y
Si2 <= M * (1 - y)

Then set your objective function to minimize 100 * Si1 + 200 * Si2.

Note: If both Si1 and Si2 have positive coefficients in the objective function, and the objective is a minimization, then you do not need the stuff after the divider line. The two constraints before the line are sufficient, because we will always want to set Si1 and Si2 as small as possible, which means setting one of them to 0.


Is the exponent bias $2^{n-1}-1$ or $2^{n-1}$ I'm a bit confused with the exponent bias. The sources I found online claim that it is either $2^{n-1}-1$ or $2^{n-1}$, $n$ is the number of bits used for the exponent. In my book when given examples on the bias of a 32bit system the bias is said to be $2^7$ which means the bias is $2^{n-1}$ while in an example on the bias of 64bit the bias is said to be $2^{11}-1$ which is $2^{n-1}-1$

So which one is it?

Both encodings for the exponent are possible, and they are called Excess-$2^{n-1}$ and Excess-$2^{n-1}-1$ - in particular, you might meet such number encodings as Excess-127, Excess-128, Excess-1023 and so on.

The IEEE-754 standard happened to choose the Excess-127 and the Excess-1023 encodings for exponents, so these encodings became more customary. Your book is not mistaken about the exponent bias, it just follows a way, different from this standard.

You can find additional information and nice graphs here.


Why is fail[1] in KMP Algorithm always 0? I'm studying KMP Algorithm. In the failure function (or the sp table), why do we always assign the value 0 to the first element (character) of the pattern? I understand about the later elements of the pattern, as we assign the sp values according to length of correctly matched suffixes and prefixes, but why does the sp value of the first element has to be 0?

This is by definition, since:

  For each position i in pattern P, spi is defined as the length of longest proper suffix of P[1...i] that matches a prefix of P.

So, we can conclude that for i=1 the length of longest proper suffix that matches the prefix is 0 since longest prefix = suffix = EMPTY_STRING.

Visit this page for details.


Regular expression at least 2 out of 3 consecutive characters should be 1 How can I build a regular expression that, using only the concatenate, union and star operations, over the alphabet {0,1}, describes the language "Every three consecutive characters contain at least two 1, and the input has length at least 3"? For instance 110011, 0101 and 11 should be refused. I was thinking on using the logic from this (incomplete) DFA, but I can't figure out how to get a regular expression that follows the rule. Thanks!

Assume that string $s$ is in $L$. We will look at the last two characters of the string:

00, impossible, because this string could not be in $L$.
01, next character must be 1, new last two characters is 11.
10, next character must be 1, new last two characters is 01.
11, next character may be 1 or 0, new last two characters is 10 or 11.

Note that no matter your current state, you will always pass through the 11 state within two steps. Assuming that $s$ ended with 11, we get the following loop:

(1|(011))*

This will be the middle section of any string in $L$. All we need to do now is handle possible prefixes, making sure not to allow any with size < 3:

(111|011|1011|11011)

And finally, possible suffixes (note the empty union to express that the suffix is optional):

(|0|01)

Now all that's left is to concatenate them:

(111|011|1011|11011)(1|(011))*(|0|01)


Can the complement of an unrecognizable language be a recognizable language? I know that complement of a language that is recursively enumerable, but not recursive, is definitely not recursively enumerable (or unrecognizable). So my question is what can be said about the complement of an unrecognizable language?

Sure: the Halting language (sometimes called $K$) is recursively enumerable whereas its complement ($\overline{K}$) is famously not.

Generally speaking, the existence of such languages follows from the implication you state -- the complement of enumerable yet undecidable languages can not be enumerable -- by the existence of precisely enumerable yet undecidable languages.

That said, there are also non-enumerable languages whose complement isn't either.


Finding the complexity of a recursive method An assignment question asks me to find the complexity of a [tail] recursive algorithm, copied below. While I understand all the complexity specifics, for example that the while loop's complexity is $n-1$ and the complexity of setting $j$ to $0$ is 1, I don't understand how I could trace the code recursively, that is within itsel - it's too hard to keep track of.

What I tried doing, is turning the algorithm into an iterative one, by simply putting all the code into a big while loop and thus avoiding the recursive call. But I'm not sure if this affects the complexity of the original algorithm.

Algorithm MyAlgorithm(A, n)
   Input: Array of integer containing n elements
   Output: Possibly modified Array A
     done ← true
     j ← 0
     while j ≤ n - 2 do {
       if A[j] > A[j + 1] then {
       swap(A[j], A[j + 1])
       done:= false
       }
     j ← j + 1
     end while
     j ← n - 1
     while j ≥ 1 do
       if A[j] < A[j - 1] then
       swap(A[j - 1], A[j])
       done:= false
    j ← j - 1
    end while
    if ¬ done
       MyAlgorithm(A, n)
    else
      return A

You have to analyze the circumstances in which your algorithm makes a recursive call. That is, when is  not done true? Well, your it's true whenever your algorithm is required to make a swap in one of its passes over the array (one of the while loops). To analyze the total worst case running time, determine the maximum number of recursive calls, and add up the total work in each of these calls. In some recursive algorithms, the amount of work in each recursive call might be different. Is that the case in your algorithm?


Concatenated pseudorandom generators I have two pseudorandom generators $G_1$ and $G_2$ from $k$ bit to $2k$ bit. I have another PRG $G_3$ from $k$ to $2k$ bits. Now I buildup a new function from $k$ to $4k$ as follows:

Let $x$ be $k$ bit then apply $G_3$ on it on $x$. Then let output by $y$.   Apply $G_1$ on first $k$ bits and $G_2$ on last $k$ and join the resulting output. Then resulting function is a PRG. How do you prove this?

The idea is to use a hybrid argument. Let us first write a formula for the new PRG:
$$
G(x) = G_1(G_{3,1}(x)) G_2(G_{3,2}(x)),
$$
where $G_3(x) = G_{3,1}(x) G_{3,2}(x)$.

Suppose that we could distinguish between $G(U_k)$ and $U_{4k}$, where $U_n$ denotes $n$ random bits. Consider the following sequence:
$$
G(U_k); G_1(U_k) G_2(U_k); U_{2k} G_2(U_k); U_{4k}.
$$
By assumption, we can distinguish between the first distribution and the last distribution. Hence we can distinguish an adjacent pair of distributions.

If we can distinguish $G(U_k)$ and $G_1(U_k) G_2(U_k)$, then this gives a distinguisher for $G_3$.
If we can distinguish $G_1(U_k) G_2(U_k)$ and $U_{2k} G_2(U_k)$, then this gives a distinguisher for $G_1$.
If we can distinguish $U_{2k} G_2(U_k)$ and $U_{4k}$, then this gives a distinguisher for $G_2$.

By assumption, $G_1,G_2,G_3$ are all secure, so we obtain a contradiction.


Computing a subproduct tree Consider the following description of a subproduct tree.

We define a tree T for some points x[0] to x[n-1], and define m = log_2(n).

Tree T is represented as a matrix where each row-column entry i, j is the product of pairwise nodes in the row above it. In total, there are m rows; the 1st row is has n column entries, and the last row has 1 column entry.

In short, how does one compute the coefficients for a large n? Once m > 4, the coefficients of the entries become greater than 64-bits. Consider the product of (x - i) for i = 0 to 15. The coefficients become very large.

Unless we are working in a finite field, it seems as though one cannot construct such a subproduct tree for say n = 2^20.

Formally: http://specfun.inria.fr/bostan/publications/BoSc05.pdf

Addendum:

I understand the complexity of the operation, as stated in the next section of the paper. However, I'm unsure how one would practically approach computing the coefficients of this subproduct tree as size n grows to be large (say 2^20).

Ex, consider the following simple example:

How does the computation scale?

Keep reading!  The paper describes how this scales for $n$, in the very next line after the excerpt you show.  In particular, the next line is Proposition 1, which states the running time of computing the subproduct tree, as a function of $n$.  That tells you how the running time scales for large $n$.

How do you compute the coefficients?

Follow the algorithm described in the paper!  You already described the algorithm.  Use exactly what you described.

Don't the coefficients become large, when $n$ is large?

Yes, potentially.  This is inherent to the task: if you want to compute some polynomial (the product) whose coefficients are large, then yes, the coefficients produced by such an algorithm will be large.  This is pretty much a tautological statement.


Finding nested intervals efficiently The intervals are represented as two numbers, e.g. $(4.3, 5.6)$. The intervals are unique.

If for $(x,y)$ and $(u,v)$, $x≤u$ and $v≤y$, $(u,v)$ is nested in $(x,y)$

How do I find out which intervals are nested in others efficiently?

The hint is to use two induction hypotheses: one to assume you can solve the problem for $n-1$ intervals, another that you can find the largest right endpoint for the $n-1$ intervals.

How do I use this information to do the inductive step in constant time?

This problem is as hard as comparison sorting, given n input number sort them.

You can make interval set from input number set $S$ (w.l.o.g suppose input numbers are in $Z^+$) as follow:

$ \Gamma = \{(a,b) \mid a\in S \wedge b=\max_{t\in S} \{2\cdot t - a + 1 \} \}$

Above transformation can be done in $O(n)$.

But if you find a nesting relation in this interval set in $o(n \log n)$, you can sort input array in $o(n \log n)$, But comparison sorting barrier is $\Omega(n \log n)$, So the algorithm which finds interval nesting cannot be better than $\Omega(n \log n)$ with respect to comparision sorting barrier, But also $O(n \log n)$ algorithm is trivial.


Fastest way to find natural solutions to Linear equation $$
a_i * x_i + b_i * x_j = N
$$

$\text{given } a_i, b_i, N \in \mathbb{N}$

i want to find a solution where $x_i, x_j \in \mathbb{N}$ or output if there exists none.

What is the fastest way to calculate this?

We can write $N$ as a linear combination of $a$ and $b$ if and only if $N$ is a multiple of $d=\gcd(a,b)$. Using the extended Euclidean algorithm we can find integers $x,y$ such that $ax+by=d$ and this in turn yields a solution of the form $\frac{N}{d}(ax+by)=N$. Now $\frac{Nx}{d}$ and $\frac{Ny}{d}$ will not necessarily be positive.

However, for all integer $k$, $a\frac{Nx+bk}{d}+b\frac{Ny-ak}{d}=N$ will also be a solution. To determine whether the equation has any natural solutions, we must simply determine the range of $k$ for which $Nx+bk$ is positive and the range for which $Nx-ak$ is positive and determine whether the ranges overlap.

In the case with 3 unknowns, $ax_1+bx_2+cx_3=N$, note that $bx_2+cx_3$ will always be a multiple of $\gcd(b,c)$. The problem thus comes down to solving $ax+y\gcd(b,c)=N$, picking an appropriate solution to that problem, and then solving $bx_2+cx_3=y\gcd(b,c)$. However it is not clear to me how to pick $y$ so that the second problem can be solved.


Finding a function f(n) which will bring T(n) runtime to O(log^4(n)) (Interview question) I am having trouble finding the solution to this interview-like question:

$T(n)$ is given as:
$$T(n) = \begin{cases} 1 & n \leq c, \\ 2T(f(n))+1 & n > c, \end{cases}$$
where $c$ is some constant.
Find a function $f(n)$ so that $T(n) = \Theta(\log\log\log\log n)$.

I'm solving the case where $c=1$. Doing it for arbitrary $c$ is made in a similar fashion.

Let take $f(N) = 2^{2^{2^{\sqrt{\frac{\log^{[3]} N}{2}}}}}$.
so that for every integer $N$ we have :
$$T\left(2^{2^{2^N}}\right) = 2 T\left(f\left(2^{2^{2^N}}\right)\right)+1
= 2 T\left( 2^{2^{2^\sqrt{N/2}}} \right)+1.$$

I'm assuming in your question that you are only interested in functions $f$ that are increasing over $\mathbf{N}$.
Let prove that $T(N) = \Theta(\log^{[4]} N)$, that is proving that there exists two positive constants $A,B$ such that for sufficiently big $N$, $$ A\log N \leq T\left(2^{2^{2^{N}}}\right) \leq B\log N.$$

Let assume the last inequality holds up to some $\sqrt{N}>1$, with constant $A=1$ and some  $B > 1$.
Then
$$f\left(2^{2^{2^N}}\right) = 2 T\left( 2^{2^{2^\sqrt{N-1}}} \right)+1,$$
and so by hypothesis:
$$\log N = 2 \log\sqrt{N/2} +1 \leq  T\left(2^{2^{2^N}}\right) \leq 2 B\log\sqrt{N/2}+1 = B \log N +1-B \leq B\log N.$$

We can then conclude by induction, jumping by successive squaring, using the increasing property of $T$ to fill the gaps.


What is the most used way to write for-loop as pseudocode? for $e\leftarrow1$ to 8 do
for $e\in[1,8]$ do
for $e\in\{x\in\mathbb{N}|1\le x\le8\}$ do

What is more preferred?

Just use whatever is clearest in your particular situation. Pseudocode is not a formal language with formal syntax.

Note that for $e\in [1,8]$ do doesn't necessarily imply that the values $1$, $2$, ..., $8$ are assigned in any particular order.  Note that $\{x\in \mathbb{N}\mid 1\leq x\leq 8\}$ is somewhat redundant: an algorithm can't possibly loop over all the reals or rationals between $1$ and $8$, so the set can only really be a set of natural numbers. Finally, note that the association $\mathrm{e}=2.71828\ldots$ is very strong, so $e$ is often a poor choice of variable name.


Undecidability of "is this CFG prefix-free?" I'm having difficulty proving undecidability of "is this CFG prefix-free?". (this proof is given as problem 5.32b in Sipser 3rd edition).
Another thread has the very different question "is this regular language prefix-free". One of the answers in that thread claims to prove undecidability for CFLs (even though that did not explicitly ask for a proof of undecidability for CFLs) using the usual Post Correspondence Problem (PCP) method.
The proof in the other thread claimed (as of Oct 11, 2020) that a certain CFL with an endmarker $\#$ is prefix free if and only if there's no PCP solution. However, it seems to be possible to have prefixes in the CFL even without any PCP solutions, which would mean the proof is wrong.
I also tried using the fact that "non-emptiness of intersection of two CFGs" is undecidable. However, we are only able to use undecidability of CFGs being prefix-free to prove undecidability of intersection non-emptiness, not the other way around.

One endmarker is insufficient to prove this. Instead, we must use multiple endmarkers. Here's the full proof, with the same basic idea taken from the other answer.
Using the notation from Sipser 3rd edition problem 5.21, let the string pairs $(t_i, b_i)$ for $i \in \{1, 2 \ldots k\}$ be an instance of the PCP problem. Define grammar rules $T \rightarrow t_i T \texttt{a}_i$ and $T \rightarrow t_i \texttt{a}_i$ (where $\texttt{a}_i$ are new symbols) along with $B \rightarrow b_i B \texttt{a}_i$ and $B \rightarrow b_i \texttt{a}_i$. This instance of PCP has a solution if and only if $T \cap B$ is non-empty. (This construction can be used to prove many other undecidability properties of CFGs; for more, see Sipser 3rd edition chapter 5 or Hopcroft and Ullman 3rd edition chapter 9).
Define more rules $W \rightarrow T\#$ and $W \rightarrow B\#\#$, where $\#$ is another new symbol. Clearly, $W$ is prefix free if and only if $T \cap B$ is non-empty. Hence, a decider for prefix-free CFGs would also decide any PCP problem. Since PCP is undecidable, we have a contradiction, and thus the language of prefix free CFGs is also undecidable.


Regarding time complexity of multi-tape Turing machines So let's say I've implemented an algorithm running in $O(n^2)$ on my 3-tape TM. What kind of time complexity would I expect for a single-tape TM?

I just don't know where to get started...

Multi-tape Turing Machine running in $O(f(n))$ can be simulated by a single-tape Turing machine running in $O(f^2(n))$.

Try writing a single-tape Turing machine that stores symbols from your $3$ tapes on its one tape, separated by some unique symbol not in $\Sigma$.

hint: For every step of your $k$-tape machine, a one-tape machine must first do at most $k\cdot n$ steps to find the position.


On the time complexity of finding independent sets in hypergraphs I am interested in the complexity of the following problems:

(a) Finding an independent set of a fixed size in an arbitrary hypergraph
(b) Finding an independent set of maximum size in an arbitrary hypergraph

It is well known that the analogues of (a)  and (b) (say (a') and (b')) for graphs are NP-complete and NP-hard, respectively. However, I am having trouble finding references for the complexity of (a) and (b). In fact, all of the papers I've been able to find on these two problems (for hypergraphs) just cite the fact that (a') and (b') are NP-complete and NP-hard, as if these results trivially generalize to (a) and (b). Is this actually the case? If not, can anyone provide references that prove the complexity of (a) and (b)?

The ubiquitous principle is that a generalized problem is at least as hard to the original problem. This rather trivial principle is applied as truism in most if not all papers.

Here is a specific version of that principle for the case of time-complexity.

Lemma. Let $A,B, C$ be three languages such that $A= B\cap C$ and $A\not=C$. ($C$ is considered as a generalization of $A$.) It takes polynomial time to determine whether $x\in B$. Then deciding $C$ is as least as hard as deciding $A$ modulo polynomial time. If $A$ is NP-complete and $C$ is in NP, then $C$ is NP-complete.

Proof. Let $\beta$ be a polynomial-time algorithm that decides $B$. Suppose we have an algorithm $\gamma$ that decides $C$. Let $\alpha$ be the following algorithm:

Given input string $x$, run $\beta$ to determine if $x\in B$. If not, return no. If yes, run $\gamma$ to determine if $x\in C$. If not, return no. Return yes otherwise.

It is routine to check that $\alpha$ return yes if and only if the input is in $A$, i.e., $\alpha$ decides $A$. Since $\beta$ takes polynomial time, deciding $C$ is at least as hard as deciding $A$ modulo polynomial time.

It follows immediately that if $A$ is NP-complete and $C$ is in NP, then $C$ is NP-complete.

Let

$A=\{\langle G,s\rangle \mid \text{ there is an independent set of size }s\text{ in an ordinary graph G}\}$. (I use the phrase "ordinary graph" or simply "graph" to contrast with "hypergraph". "General graph" sounds more like hypergraph. Indeed, hypergraph is a generalization of an ordinary graph.)
Let $B=\{\langle G\rangle\mid G \text{ is an ordinary graph}\}$.
Let $C=\{\langle G, s\rangle \mid \text{ there is an independent set of size }s\text{ in a hypergraph G}\}$.

The lemma tells us that deciding $C$ is at least as hard as deciding $A$.

Exercise 1. Explain that deciding whether a graph is 3-colorable is at least as hard as deciding whether a given planar-graph is 3-colorable. (In fact, both problems are NP-complete.)

Exercise 2. Prove that it is NP-complete to determine whether there is independent set of given size in a given triangle hypergraph. A triangle hypergraph is defined as a hypergraph where each edge is a set of 3 vertices.


What language does this deterministic finite automaton accept? Been mulling over this one for hours, my initial thought was { w ε {a,b}* | w is empty, or ends with either ab or ba} but that's clearly wrong as neither aba nor bab are accepted by the automaton. If anyone has any idea what language this automaton accepts it would really put my mind at ease.

$(a^+b \mid b^+a)^*$. I am not sure there is a "simple" description of your language in plain English, but directly from the regex you get that it is the language that has the empty string and all strings that can be partitioned in such a way that each part is either multiple $a$'s (at least one) followed by one $b$, or vice versa.
In my opinion the regex and the automaton describe the language better than a "natural language description" in this case.


Implement data structure with efficient insert/findKthSmallest operations I was asked this question by an interviewer. I tried solving it using an array, such that I make sure the array in sorted when I insert. However I don't think this is the best solution. What would be a good solution for this problem?

Make an augmented search tree. This is an ordinary binary search tree, where each node additionally stores the number of elements in its subtree.  This data structure is known as order statistic tree.

If we balance the BST (making it an AVL tree for instance) then insertion can, of course, be done in logarithmic time (incrementing the node count along the search path).

Also finding the k-th element is logarithmic time. Let $n$ be the number of nodes in the left subtree of the root. If $k=n+1$ we return the root. If $k\le n$ we continue in the left subtree. If $k>n$ we return the $k-(n+1)$-st node in the right subtree.


Does the rebalancing propagate upwards only to update the height of the nodes in an AVL tree? I was studying AVL trees and was wondering if the only reason one propagates upwards to the node in an insert is to change the height. It seems to me that rebalancing does not recursively propagate back with only inserts but one might have to go back to change heights (since only nodes on the path from insertion point to root node have possibly changed in height, so we need to make sure we update them).

However, I was trying to form some type of proof that we don't actually recurse to the root and actually perform rebalancing. The proof I sort of had was the following:

The only way to recurse back to fix a unbalanced node is if we have two violations due to an insertion. One at some point down the tree and another one higher up the tree. When we do an insert the node increased height which caused these two unbalances. For us to have to recurse back we need to make sure even after the rebalancing of the lowest node, that the height doesn't decrease due to the rebalancing. This is unfortunately unavoidable because for that to happen, we'd need to be in one of the cases of rebalancing where the node's height doesn't change. Since the height of a node always decreases in an insert, then we don't actually need to rebalance.

Why don't we need to rebalance? That is because the only time we need to rebalance and the height doesn't change is when the right child of the lowest violating node $x$ has two subtrees that are balanced. That is not possible to happen because for that to happen, you need two inserts to cause that unbalance, but a single insert would cause the imbalance already, so the second insert won't make the right child of $x$ have two balanced subtrees.

You may have to rebalance during insertions, that much is clear: inserting a sorted sequence of values would otherwise lead to a degenerate tree.

By looking at the setup graphics of the four types of rotation, you can easily see that the height of the affected subtree after the insertion is the same as before. Thus, no node outside of this subtree can be imbalanced.

Thus, we never need more than one rotation when inserting. We can stop moving up the tree after we've rotated once, and efficient (non-recursive) implementations do exactly that.