What are Surnames' dataset usages? I have found a dataset which involves surnames dispersion around the world that sorted by population which I use it for a name recommender system.

Its readme page caught my attention because it has mentioned that suitable for cybersecurity and ML fields. Unfortunately on I'm a newbie person in these fields, and I can not understand how it is proper in other topics such as the mentioned topics.

On the other word, I would like to know how sort of names is usable on other topics?

The readme file lists the following uses for the dataset:

1. Cyber Security

2. Machine Learning

3. Recommender System

I believe that you already know point 3 since you specified that you want to use the dataset to build a recommender system.

About Point 2: You can use the information in the dataset to train a machine learning algorithm. The former could, for example, learn to recognize the relationships between surnames and nationality, therefore, after the training, you could pass one or more surnames as an input to the  algorithm and it could return the country.

About Point 3:
Here the subject becomes wider:
such a database can have great potential in the field of security.
 For example it could be used to perform password penetration tests, towards servers, using the list as a dictionary. For this same reason, however, it could also be useful to any attackers with malicious intent. Another example: imagine you have gained access to a confidential database that stores all user passwords and usernames. However, these data are hashed. You could submit all dataset records to the same hash function and compare them with database hashes to see if you find matches.


Condition to prove $f$ is a reduction A theorem says if $f$ is a computable function and we can prove $x \in A \Leftrightarrow f(x) \in B$, then we can use reduction so $A \leq_m B$.
But i'm confused if should I prove if :

$(x \in A \Rightarrow f(x) \in B )\land (f(x) \in B \Rightarrow x \in A)$

Or

$(x \in A \Rightarrow f(x) \in B ) \land(x \notin A \Rightarrow f(x) \notin B)$

in which circunstances because I've seen both in demonstration. Or maybe are they equivalent ?
For example, here is a solution to the empty string problem. But with $f$ such as, $f: \text{M accepts w} \to \text{M accepts } \epsilon \\ f(\langle M, \epsilon \rangle) = \langle M \rangle$, we can proove 1. Is it valid ?

It is called contraposition :
$f(x) \in B \Rightarrow x \in A$
is equivalent to
$x \notin A \Rightarrow f(x) \notin B$.
So, the two statements that you have seen are equivalent as well.


Floyd Warshall's All pair shortest path problem does not evaluate all possible paths We know that the FW all pair shortest path is a Dynamic Programming (DP) approach to solving the problem. Being a DP, it smartly evaluates all possible options before deciding the final option at each stage.

I have manually evaluated and traced a 5 node graph with this algorithm. The actual graph is not important here. I will take the example of the evaluation of path(V4,V5) in iteration 1 and 2 only:

Stage 1: min{(4,5),(4,1,5)} of Stage 0

Stage 2: min{(4,5), (4,2,5)} of Stage 1

So if we expand this, then by the end of Stage 2, we have actually essentially evaluated the paths {(4,5) , (4,1,5), (4,2,5), (4,2,1,5), (4,1,2,1,5)} and selected the minimum.

As seen, we are evaluating cyclic paths as well e.g. (4,1,2,1,5) from above. If we continue tracing the algorithm till the end, we find that we never evaluate the path (4,2,1,2,5) for this specific example. Does this mean, not all paths are evaluated with this algorithm? I know not evaluating it won't harm as it will definitely not be the shortest path but my point is that should have been the case with (4,1,2,1,5) too. It looks like although the output is correct and consistent, yet theoretically speaking certain paths are not evaluated because of the way the algorithm is structured and not out of merit. Am I missing something here?

Yes, the path $(4,2,1,2,5)$ is not evaluated.
However this is not a problem.

Since we assume that the graph doesn't contain any negative cycles (this is a requirement for FW), there exists an optimal path for each pair of nodes that doesn't contain any cycles.
Therefore the algorithm only needs to guarantee, that cycle-less path gets evaluated.

By induction you can show that this is always the case.
Let $k$ be the variable in the most outer loop.
Induction hypothesis: After the $k$th iteration the table contains all the shortest paths between each pair that only uses nodes $\le k$ on the path (without start and end node).

At the beginning this is trivially true.
And also the induction step, going from $k$ to $k+1$, is pretty easy to show:
A minimal path using only nodes $\le k + 1$ from $u$ to $v$ either contains only nodes $\le k$, or it contains a minimal path from $u$ to $k+1$ combined with the minimal path from $k+1$ to $v$. (Here we use the fact that the paths contain no cycles. If a path contains cycles, this statement ca be wrong.)
And exactly this case is handled in the algorithms.

Therefore at the end the table contains all minimal paths.


Is per-record timeline consistency is somehow equivalent to causal consistency? What I understand about per-record timeline consistency is:

  For a specific primary key all the insert/update/delete operations should
  be read in the same order by all replicas.

Since all modifications to a specific primary key are causally related (a client reads it, then modifies or delete it), then per-record timeline consistency is somehow equivalent to causal consistency. If they are essentially equivalent, then why put another name on it? Am I missing something?

You may know that per-record timeline consistency is used in PNUTS: Yahoo!’s Hosted Data Serving Platform:

  We provide per-record timeline consistency: all replicas of a given record apply all updates to the record in the same order.

Answer your questions:

  Since all modifications to a specific primary key are causally related (a client reads it, then modifies or delete it), ...

They are actually totally (or sequentially) ordered, stronger than "causally related".

  ... then per-record timeline consistency is somehow equivalent to causal consistency.

Given the reason above, per-record timeline consistency is more like sequential consistency (wiki). In fact, per-record time consistency is also called per-key sequential consistency, which is stronger than per-key causal consistency. Because sequential consistency is not local, per-key sequential consistency is not equivalent to (i.e., weaker than) sequential consistency defined over multiple keys.


Advantages and disadvantages of microcoded vs hardcoded architectures Preamble
I can't understand what are the advantages and disadvantages of microcoded processor architecture and hardcoded one.
Basically what I understood is that a microcode architecture divides an istruction in more microinstructions. I didn't found much documentation written in a simple way (too much complicated) so I'm asking you: what are the advantages and disadvantages of each one?
Due to the large amount of aspect of this "subject", I'll recap the question into three main aspects:
Question (architectural point of view)
A microcoded architecture should semplify the design of each instruction, it means that it's do much more difficoult to design a full hard coded processor?
Or maybe hardcoded archtecture is suitable for microcontrollers or smaller design?
Question (performance point of view)
Wikipedia (not the most reliable source, I know) says that a microcoded architecture is a little slower than an hardcoded one. It also says that microinstruction are used to build complex instruction, but these are not commonly used because programmers prefer high level languages, and compilers prefer using simpler but faster instruction.
From this point of view, is still necessary to design microcoded processor?
Question (functional point of view)
If microcoded archtectures help the creation of complex instruction (= easier assembly development?), hardcoded ones help programmers in any way during their work? This seems a stupid question but I think it's not.
Looking at this site of assembly game programmers (I hope I can post that link, FAQ says to share your research), one guy says that HuC6280 processor has the best instruction set because:

Fav[ourite]: HuC6280.  Basically a 65CS02 set (Rockwell's added instructions). Optimizing is soo much fun. There are some super crazy optimizations for this style chip out there. I know people will fight to the death (or possibly argue) that it's not RISC, but it definitely had some precusor ideas of RISC. A very small, simple, but fast instruction set (hard coded, not microcoded), a large set of 128 16bit address registers (also halved as 256 8bit data registers). The immediate operand instructions are very fast and lend themselves perfectly for self modifying code. The downside is the small logical address range of the PC. All optimizations have to be made local and very specific. Look up tables (LUTs) need to be organized accordingly (and interleaved for 16bit and wider data elements).  One thing I never understood is why they never implemented immediate operand opcodes as 1 cycle instead of 2, since the chip would perform a fetch cycle while operating an ALU operation on other opcodes. Same for implied instructions (flag changing).

He seems to be very excited about that architecture. One point to hardcoded design?
However, I found that HuC6280 is an 8bit processor, it is much much simplier than modern ones. It means that hardcoded would be preferrable if its design wasn't so hard? EDIT: He also quote self modifying code, which is not commonly used today (due to high level programming maybe) but for assembly programmer is quite an important feature.
Examples
I know that this is an hard question, explanation might be long. If you (guy with much more experience than me) want to answer, may you add some example of hardcoded architecture? It would be much appreciated. Both modern and deprecated are ok
And thanks for reading all this poem

The distinction between "microcoded" and "hardcoded" multi-cycle control units is a relatively small implementation detail.  The distinction was more important in the 1950s when people were inventing new implementation techniques for state machines.  In modern processor design there are much more important implementation distinctions, like how much pipelining and instruction overlap you are going to try to achieve, whether you are going to speculatively execute instructions, and whether you are going to try to schedule instructions out-of-order.

That said, here's the distinction:  We divide the design into datapath and control.  Here's the picture of the MIC-1 from Tanenbaum's Computer Organization book.  (The image is by Suyog.karnawat, from Wikimedia commons.)  Everything in the design is the datapath except the box in the upper right hand side that says "Instruction decoder and control logic."

The "Insruction decoder and control logic" box is a finite state machine.  The datapath in this example is very simple, with only a single bus, so even an instruction to add two registers and put the result in a third register takes multiple cycles (each of which corresponds to a state in the state machine.)

Each instruction goes through the following steps/states (each of which takes a cycle)

move the PC (Program Counter) to the MAR (Memory Address Register)
assert the controls to perform a load from the memory bus
eventually the memory will return the requested data (which corresponds to the next instruction) and put it in the MDR (Memory Data Register)
move the instruction from the MDR to the IR (Instruction Register).  At this point the instruction gets decoded and we figure out what to do with it.  In this case it's an add operation so we know we need to:
move Ra to the X register
put Rb on the bus (so that it will go to the B input of the ALU) assert the ALU control lines and Mux select appropriately to do an add operation, the result of which will get saved in register Y
Move Y to the Rc register, and then every non-branch instruction ends by incrementing the program counter:
Put the PC on the bus, set up the ALU to increment (Select the MUX to put constant 1 on the A input and set up the ALU to Add) so that PC+1 will get saved in the Y register
Move the Y register back to PC

So 9 state transitions to perform a simple add instruction.

So the "Instruction decoder and control logic" is a finite state machine with inputs from the IR register, outputs are the control signals, and there must be some flip-flops inside to represent the state of the state machine.  But there are lots and lots of ways to implement a state machine.

$\lceil \log_2 N \rceil$ flip-flops (where $N$ is the number of states) and a lot of combinational logic (to calculate the control signals and next state).
$N$ flip-flops with one-hot encoding and a bunch of combinational logic (usually less than with option A, but a lot.)
Somewhere between $\lceil \log_2 N \rceil$ and $N$ flip-flops with some combinational logic of intermediate complexity.

And the combinational logic for the control signals and next state functions can be implemented any number of ways:

As NAND gates reduced (using Quine-McCluskey, or whatever) to sum-of-products form.
As NAND gates reduced to some relatively efficient multiple-level circuit.  (This is probably what people think they mean when they talk about "hardwired control.")
A design using Multiplexers for the combinational logic
A design using Programmable logic arrays (although I don't know if you can even buy these anymore.)
A design where the combinational logic is implemented with a ROM.  (This is probably what people think they mean when they talk about "microcoded control.")  The ROM might be a EEPROM so that it is somewhat easier to modify if you find a bug.

ROMs can get really huge if you're not careful.  For example a ROM-based design would almost always use $\lceil \log_2 N \rceil$ flip-flops, because making the state wider also makes it sparser, which is sometimes good for gates but not for ROMs.  Also, you would only use the opcode bits as part of the address to the ROM, not the register specifiers and such.

Finally with ROMs you might choose to make the microcode word wide (the microcode word produces the entire set of bits for the control signals) or narrow (the microcode word chooses one of a smaller number of possible control signal combinations and then there's a second ROM that translates from that smaller number to the actual required control signals.

So the distinction between "hardcoded" and "microcoded" is only one very small decision that needs to be made among hundreds of design decisions.  And it's certainly not the most important one.  (For example, you could choose to put a second bus on the datapath, which would enable you to perform some instructions with a lot less cycles.)


Proof of sparsification lemma: What exactly does the $\pi$ operator do? In their proof of the sparsification lemma, Impagliazzo et. al describe the following operator $\pi$:

For a familiy of sets $\mathcal{F}$, let $\pi(\mathcal{F}) \subseteq \mathcal{F}$ be the family of all sets $S$ in $\mathcal{F}$, such that no other set $S'$ in $\mathcal{F}$ is a proper subset of $S$.

I am trying to understand what this operator does. So far, I thought that it could be calculated by the following algorithm:

$$ \text{While}~\exists S_i, S_j \in \mathcal{F}: S_i \subset S_j  \text{do} \\ \mathcal{F} \leftarrow \mathcal{F} \setminus S_i$$

By the rest of the proof seems to indicate that actually, one has to remove the superset:
$$ \text{While}~\exists S_i, S_j \in \mathcal{F}: S_i \subset S_j  \text{do} \\ \mathcal{F} \leftarrow \mathcal{F} \setminus S_j$$

Which leads me to believe that I did not fully understand the description of the operator. What would be an algorithm to calculate that $\pi(F)$?

From the definition you gave, the supersets have to be removed, as you want to keep only those sets for which there is no proper subset in $\mathcal{F}$.

For example:

In blue are the sets of $\mathcal{F}$ which don't have proper subsets in $\mathcal{F}$, in red are the ones who do. You want to keep the blue ones, by definition of $\pi$.


Why doesn't greedy work for Clique? In reference to this problem (equivalently, findind a maximal clique in an undirected graph), I believe greedy approach should work (i.e. removal of people who have maximal qualms with others.). Though I cannot prove that this would always work or won't but I intuitively felt that it should, but eventually some examples could be created that fail this greedy approach.

Can someone prove/disprove whether the greedy approach is correct? Not just a counterexample, but a general explanation would be quite useful.

Consider the graph consisting of a clique on $n/3$ vertices and a complete bipartite graph with $n/3$ vertices on either side. The degree of each vertex in the clique is $n/3-1$, whereas every vertex in the bipartite graph has degree $n/3$. Your algorithm would thus remove all the vertices in the clique. The remaining graph is bipartite, and so its maximal clique contains only two vertices.

So your algorithm finds a clique of size two instead of a clique of size $n/3$.


Basic requirements for Integrality gap examples I have the following question about giving a series of examples of range spaces for my Hitting Set problem that establish a lower bound for the integrality gap (IG).

IG is the supremum of ratio of the optimum for natural integer linear programming (ILP) formulation of Hitting Set to the optimum for its (mean ILP) LP-relaxation taken over all range spaces corresponding to my problem.

There are lots of algorithms where solution for LP-relaxation is rounded to some feasible solution of ILP which is not far from optimum. IG gives the lower bound of multiplicative factor to which rounding procedure could worsen the optimum for LP with respect to the goal function.

Specifically, do I need to provide any polynomial algorithm for generating those series of example range spaces (giving the gap lower bound) ? if yes, then what are the parameters with respect to which my algorithm should be polynomial in ?
I'm interested in this because by claiming some gap lower bound I provide  educated lower bound for approximation algorithm performances which are based on aforementioned LP-relaxation.

No, there is absolutely no need for the gap instances to be efficiently constructible. It is perfectly fine even to give some pure existence proof, say using diagonalization or probabilistic techniques.

The reason is that the integrality gap examples rule out certain kinds of algorithms. Specifically, suppose that an algorithm solves the LP and then rounds it, and suppose that the way you prove the approximation guarantee is by showing (for a minimization problem) that rounding increases the value of the solution by at most a factor $C$. If there is an integrality gap of $\alpha$ then you know that $C \geq \alpha$. So no algorithm with this kind of analysis can result in an approximation ratio better than $\alpha$.

If I remember correctly there are some rare cases in which the way you analyze your algorithm is a bit different, and then you can go beyond the integrality gap, but unfortunately I can't think of any; if you're interested ask a separate question.

It is meaningful to consider an integrality gap even for different relaxations, for example for the semidefinite relaxation or for some LP or SDP hierarchy. The requirements are the same only you're comparing the integral optimum to the value of some more complicated program. The consequence is that an algorithm which proceeds by solving that program and then rounding can't given an approximation ratio better than the integrality gap (unless it does some rare hocus pocus as mentioned above).

Chlamtac and Tulsiani have written a nice survey on integrality gaps, which you might want to browse. It describes many complicated methods for constructing integrality gaps.


Equivalence of two context free grammars [for the given example] I know that in general it is undecidable whether two context free grammars generate the same language, but I have to do this exercise and I am finding myself somewhat stuck:

G1:

S->e|aB|bA
B->bS|aBB
A->aS|bAA

G2:

S->e|aSb|bSa|SS

I tried to apply Arden's rule in the first grammar, to variables A and B, but I think it might be bringing me to a loop since the productions are right-recursive. I'm not really good at manipulating grammars so I don't know how to proceed in the proof.

Also, the exercise has a second question:

Show that all the words generated by G1 have even length.

I thought that if I can demonstrate that G1=G2, it is easier to conclude the proof using G2, and in fact that is something I was able to do, but I miss the fundamental equivalence so as for now I only showed the property for G2...

Both grammars generate the language of words having an equal number of a's and b's. Here are some hints on how to prove that.

Grammar $G_1$: Prove by induction on derivation length that

Every word generated by $S$ has an equal number of a's and b's.
Every word generated by $A$ has one more a's than b's.
Every word generated by $B$ has one more b's than a's.

This shows that every word generated by $G_1$ has an equal number of a's and b's. For the other direction, prove by induction on word length that

Every word having an equal number of a's and b's can be generated by $S$.
Every word having one more a's than b's can be generated by $A$.
Every word having one more b's than a's can be generated by $B$.

This part is more complicated, though the different cases you have to consider follow closely the rules of the grammar.

Grammar $G_2$: Easy induction on derivation length shows that every word generated by $S$ has an equal number of a's and b's. For the other direction, prove by induction on the length of the word that every word which has an equal number of a's and b's can be generated by $S$, as follows.

Given a word $w$, consider the walk generated by $w$ starting at the origin in which $a$ corresponds to a step up and to the right and $b$ corresponds to a step down and to the right. The walk ends on the X axis (since the number of a's and b's is equal). Let $x$ be the prefix of $w$ corresponding to the first time in which $w$ reaches the X axis (after the empty prefix), and write $w = xy$. If $y$ is empty then $x$ must start and end with different letters, so the one of the productions $S\to aSb|bSa$ can be used, and otherwise the production $S\to SS$ can be used.


Keeping a String Secret in (Open) Source Code I have finished developing an app for Android and intend to publish it with GPL -- I want it to be open source.
However, the nature of the application (a game) is that it asks riddles and has the answers coded into the string resource. I can't publish the answers!
I was told to look into storing passwords securely -- but I haven't found anything appropriate.

Is it possible to publish my source code with a string array hidden, encrypted, or otherwise obscured? Maybe by reading the answers from an online database?

Update

Yuval Filmus's solution below worked. When I first read it I was still not sure how to do it. I found some solutions, for the second option: storing the hashed solution in the source and calculating the hash everytime the user guesses. To do this in javascript there is the crypto-js library at http://code.google.com/p/crypto-js/.
For Android, use the MessageDigest function. There is an application (on fdroid/github) called HashPass which does this.

You have at least two options, depending on what problem you want to solve.

If you want innocent readers of your code to not get the answers inadvertently, or you at least want to make it a bit difficult so that users are not tempted, you can encrypt the solutions and store the key as part of your code, perhaps a result of some computation (to make it even more difficult).

If you want to prevent users from retrieving the answer, you can use a one-way function, or in computer jargon, a hash function. Store a hash of the answer, and they you can test whether the answer is correct without it being possible to deduce the answer at all without finding it first. This has the disadvantage that it is harder to check for an answer that is close to the correct answer, though there are some solutions even to this problem.


Given a sorted array with n elements and element x that is inside the array at position k, find k in O(min(logk, log(n-k))) Given a sorted array $A[1,\ldots,n]$ and element $x$ that located at
  position $k$. We know $x$, we don't know $k$. Write an algorithm that finds $k$, in $O(\min(\log k, \log(n-k))$ time complexity.

Any ideas how to solve this?

Check the first element.  Then check the last.  Then the second, then the second to last, then the fourth, then the fourth to last, then the eighth, and so on.  Stop upon bounding the location of x to a region at the front or back of the list.

Once you've bounded it you can just do a binary search.

Can you see why this works?


Is the minimum weight independent dominating set np-complete in chordal graphs? I have a found a small article [1] saying (the first paragraph of the introduction) that the minimum-weight independent dominating set is NP-complete in chordal graphs, but at the same time, seems to contradict that exact statement.

Moreover, I have found another reference [2] saying that in chordal graphs, it is polynomial time solvable. So which one is it?

Note: I am just trying to reference this result in a project of mine. No need for a proof.

Edit: I am referring to this piece of the introduction: "Domination and most of its variations are NP-complete for chordal graphs (even for the subclass of split graphs) with the exception of independence domination (see [3]). On the other hand, an unpublished proof for the NP-completeness of the weighted independent domination in chordal graphs by the author 20 years ago..." Then in my reference [2], it also states that the weighted version is polynomial time solvable, yet here they say that there is an NP-completeness proof. Am I missing something fundamental?

The weighted independent domination problem is NP-complete for chordal graphs by G. J. Chang (2004)
Fundamentals of Domination in Graphs by T. W. Haynes, S. Hedetniemi and P. Slater (1998)

As the article clearly mentions, unweighted minimum independent dominating set can be solved efficiently (in fact, linear time) for chordal graphs. A glance at the paper shows that this works even if the vertices are given $\{0,1\}$ weights (rather than all having unit weight). On the other hand, weighted minimum independent dominating set is NP-complete.


How would a CPU designed purely for functional programming be different? CPU's are to an extent designed with in mind the software that people will write for it, implicitly or explicitly.

It seems to me that if you look at the design of instruction set architectures, they are very "imperative", in the sense that each instruction encodes an imperative style command. It also seems to me that the current instruction set architectures have evolved partly based on the type of code programmers produce.

If one would design a CPU from scratch, knowing that it would only ever run programs written in a functional programming style, how would that CPU be designed differently from existing CPU's?

Actually, it has been done: https://en.wikipedia.org/wiki/Lisp_machine

One aspect in CPU design for FP is garbage collection. GC is very important for functional languages. Common implementations require that the GC can distinguish between pointers and non-pointer data. Effectively, that means storing an extra bit along your data. This is the reason that, for example, OCaml integers are only 31 bit on 32-bit architectures and 63 bit on 64-bit architectures. Integer arithmetic then involves awkward extra shifting operations. Other languages (or other OCaml data types) may waste whole machine words for that extra bit, thus using 128 bits for 64-bit integers. A CPU that is natively designed towards GC might have a 65-bit data bus but 64-bit arithmetic.

That said, a lot of non-functional languages also have garbage collection and would thus profit from respective architectures.

Another thing that comes to mind is that memory usage of FP typically is much more scattered than that of imperative programs. Mainly because it is less natural to use arrays. In consequence, these programs profit less from caching contiguous chunks of memory. So, an FP CPU might use different caching strategies.


How does BFS guarantee the minimum path for this problem? https://leetcode.com/problems/bus-routes/
You are given an array routes representing bus routes where routes[i] is a bus route that the ith bus repeats forever.
For example, if routes[0] = [1, 5, 7], this means that the 0th bus travels in the sequence 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... forever.
You will start at the bus stop source (You are not on any bus initially), and you want to go to the bus stop target. You can travel between bus stops by buses only.
Return the least number of buses you must take to travel from source to target. Return -1 if it is not possible.
The solutions for this problem involve doing a BFS from each of the vertices(bus stops), but how does that guarantee a the minimum path ?

BFS (or Breadth-First Search) from its name implies that it will search for the destination along the breadth. That means it looks at all the current possible routes ie nodes connected to the current one and divides itself into all of those. Basically, at every junction, it divides itself and continues down that path until it encounters the destination node.
So effectively, it can be said that it checks for all the paths of length len from the source node starting len from 0 and incrementing it by 1 until it reaches the destination.
Let's say it got to the destination with length 7, now this means that it tried all the paths of length 0, 1, 2 ... 6 but was not able to get to the destination.
So, this means that whenever BFS finds a path, it already tried all paths of length (or cost) lower than the current one but was able to find a complete path that reaches the destination. Which means it always finds the shortest (or cheapest) path.


Number of buckets for bucket sort (most significant bits) Wikipedia has this pseudocode on bucket sort:

  function bucketSort(array, n) is
    buckets ← new array of n empty lists
    for i = 0 to (length(array)-1) do
      insert array[i] into buckets[msbits(array[i], k)]
    for i = 0 to n - 1 do
      nextSort(buckets[i]);
    return the concatenation of buckets[0], ...., buckets[n-1]

It also explains:

  Here array is the array to be sorted and n is the number of buckets to use. The function msbits(x,k) returns the k most significant bits of x (floor(x/2^(size(x)-k))); different functions can be used to translate the range of elements in array to n buckets...

What baffles me is: Why would one want to initialize buckets with n buckets when 2^k is the maximum number of values that msbits can possibly generate, given the way it's defined?

The code you found is unfortunately written and explained in a very confusing way, most notably in a way that, in my humble opinion, misses the entire point of Bucketsort.

Let $A$ be an array of $n$ elements, taken from the ordered set $(S, \le)$. Bucketsort is a sorting algorithm that sorts $A$ in linear time with probability $1$, subject to the hypothesis that the statistical distribution of the elements of $A$ over $S$ is known in advance.

For the sake of simplicity, we will assume $S$ to be the real interval $[0, 1)$ and the distribution of $A$ to be uniform over $[0, 1)$. Our second assumption is without loss of generality. In fact, should we be provided with a different probability density function $\rho$, we could simply replace each $x \in A$ with:

$$
x' =\int_{0}^x \rho(z) dz
$$

An analogous argument holds for different choices of $S$.

Bucketsort works as follows:

Split $[0, 1)$ in $n$ consecutive intervals, where $n = |A|$, such that the $i$-th interval is $\left[ \frac{i-1}{n}, \frac{i}{n} \right)$
Create $n$ empty lists $L_1, L_2, \dots, L_n$
For each element $x$ of $A$, add $x$ to the list corresponding to the interval in which it falls
Sort each list individually, then return the concatenation $L_1 \circ L_2 \circ \dots \circ L_n$

Correctness is obvious, but complexity isn't. The crucial hypothesis is that, by assumption, we are sorting elements uniformly distributed over $[0, 1)$. Therefore, if $n$ grows large, as it is the case in the usual asymptotic setting, at the end of our third step, each of the lists will contain a constant number of elements with probability $1$; if that weren't the case, the elements wouldn't be uniformly distributed after all. Also observe that "with probability $1$" is not the same as "certainly", although it's as close as it gets.

The choice of exactly $n$ buckets is due to the fact that we want our last step to take linear time; but that can only be achieved if each list contains a constant amount of elements. We could have chosen just as well to use $n/c$ buckets for any $c \in \Theta(1)$, but we couldn't have started with $ k \in o(n)$ buckets; each of them would have contained $n/k \in \omega(1)$ elements. The total cost of sorting them would have been:

$$
k \left ( \frac{n}{k} \log \frac{n}{k} \right ) = n \log \omega(1) \in \omega(n)
$$


If an NP-complete problem is shown to have a non-polynomial lower bound, would that prove that P != NP? I understand that the Cook-Levin theorem proved that any NP problem is reducible to an NP-complete problem, which signifies that if a polynomial-time algorithm for an NP-complete problem is found, it will mean that all problems in NP can be solved in polynomial time.

My question is: does this proof also hold the other way? I.e. if an exponential lower bound for an NP-complete problem is proved, would that mean that no problems in NP can be solved in polynomial time?

Not quite.  If there's an exponential lower bound for a NP-complete problem, then it follows that no NP-complete problem can be solved in polynomial time.  However, there will be some other NP problems (which aren't NP-complete) that can be solved in polynomial time.

If there's an exponential lower bound for any NP problem, then it follows that P != NP.  In particular, an exponential lower bound for some problem means that the problem is not in P.  So, if you have an exponential lower bound for some NP problem, that means the problem is in NP but not in P -- which means NP contains a problem that is not in P -- which means that NP != P.

It might help to recall that NP is a set of problems (the set of all search problems where YES answers have a polynomial-size witness that can be verified in polynomial time).  Similarly, P is a set of problems (the set of all search problems that can be solved in polynomial time).  So, if you've found one element of NP that is not an element of P, you can immediately conclude that those two sets are not the same sets.

Or, to put it another way: your second paragraph is the contrapositive of the statement in the first paragraph.  If there is a NP problem with a non-polynomial lower bound, then not every problem in NP can be solved in polynomial time.  If not every problem in NP can be solved in polynomial time, then it follows that no polynomial-time algorithm can be found for any NP-complete problem.

See What is the definition of P, NP, NP-complete and NP-hard? for more background.


How to prove any polynomial of degree $k$ is in $\Theta(n^k)$? I want to prove that any polynomial of degree $k$ is in $\Theta(n^k)$. The coefficient of $n^k$, $a_{k}$, is positive.

I know I need $0 \leq c_{1}n^k \leq a_{k}n^k + ... + a_{0} \leq c_{2}n^k$ for all $n \geq n_0$.

The upper limit is easy to prove by taking $c_{2} = \sum\limits_{i=0}^k |a_i|$

I don't know how to prove the lower limit. Any hints?

I think I found a good way to prove $p(n) = \Omega(n^k)$:

We want to show that $0 \leq cn^k \leq p(n)\ \forall{n \geq n_{0}}$

We know $\lim_{n\to\infty} p(n)/n^k = a_{k}$

This gives us some intuition to choose $c \leq a_{k}$.

Let $c = a_{k}/2$

Now choose $n_{0}$ such that $cn^k = (a_{k}/2)n^k \leq p(n)\ \forall{n \geq n_{0}}$.

or rearranging, $(a_{k}/2)n^k \geq -\sum\limits_{i=0}^{k-1} a_{i}n^i\ \forall{n \geq n_{0}}$

or we can relax the inequality and pick $n_{0}$ such that $(a_{k}/2)n^k \geq \sum\limits_{i=0}^{k-1} |a_{i}|n^i\ \forall{n \geq n_{0}}$

or $(a_{k}/2)n^k \geq n^{k-1}\sum\limits_{i=0}^{k-1} |a_{i}|n^{i-(k-1)}\ \forall{n \geq n_{0}}$

or we can relax the inequality and pick $n_{0}$ such that $(a_{k}/2)n \geq \sum\limits_{i=0}^{k-1} |a_{i}|\ \forall{n \geq n_{0}}$ since $n^{i-(k-1)} \leq 1$

Hence pick $n_{0} = 2/a_{k}\sum\limits_{i=0}^{k-1} |a_{i}|$

We now have a $c$ and $n_{0}$ such that $0 \leq cn^k \leq p(n)\ \forall{n \geq n_{0}}$

Hence proved.


Show Resource Allocation Problem is NP-Complete We are given $n$ tasks and $m$ resources. Each task $i$ requires a set $S_i$ of resources to be active, and each resource can be used by at most one task.  The Resource Allocation problem asks: given $S_1, \ldots, S_n$, and an integer $k$, whether it is possible to allocate the resources to the tasks so that at least $k$ tasks are active.  Give a polynomial-time reduction from Independent Set to Resource Allocation

I am not sure how to construct the reduction. The difficulty I am having is the solver looks like a solver for a bipartite graph problem but we do not necessarily get a bipartite graph. Thank you!

Let's try to do some pattern matching. In independent set, we are given a graph, and want to find a maximum number of vertices satisfying some constraints. In your problem, we are given a collection of tasks and resources, and want to find the maximum number of resources satisfying some constraints. Hence it seems that tasks should correspond to vertices.

What about the constraints? In independent set, we are allowed to choose two vertices together if no edge connects them. In your problem, we are allowed to choose two tasks together if they have no common resource. Hence it seems that resources should correspond to edges.

You take it from here.


Validate that a threaded binary tree works as intended I am attempting to validate that my threaded binary tree’s insertion and deletion works as intended.

Would it be safe to assume that the following procedure would have tested all corner cases at least once?

I have an array of integer S = {1, 2, …, n-1, n} for n = 1’000’000.
I then randomize the order of S to obtain S’ and S*.
S’ is then used to insert its elements sequentially, into the tree.
After all elements are inserted, I create an in order list of the tree, say A, and confirm that A = S.
This concludes the insert test.

For deletion, I pass elements of S* sequentially as argument to be removed from the tree, testing that each call was successful. After all elements was removed I confirm that the tree is empty.

Shortly - no, it is not safe.
Huge random test does not guarantee success (but of course, when there is a bug, it finds it in the most cases).
To test threaded tree with deletion and insertion you need to have saturated all nodes (with thread links), make them change thread, the same for deletion.
To make sure it works all corner cases must be covered both for insertion and deletion. With huge input there is huge probability it works, but this is not conclusive. Also making more passes (more test) it increases probability of success, but nothing more.

To test it manually - case by case - you do not need very big tree (I did tests on double threaded AVL, tree height was maximally 5).


Machine Learning and Neural Networks for High School Students I hope this question is appropriate for this forum.
In this summer I am giving a 3-day workshop on machine learning and neural networks for advanced and very enthusiastic high school students which all know at least one programming language.
Typically a day consists of 2 hours lecture in the morning and later the students should solve a given problem (with help, of course).
For the first day we are going to sove a simple pixel counting problem in a picture (Or do you know any simpler interesting example)
For the second and third day I wanted to give them a more challenging problem:
Consider the set of binary $3\times 3$ matrices. One can imagine every matrix as a chessboard like picture where every $1$ corresponds to a black field and every $0$ to a white field. The objective is to count the connected components.
I allready produced the matrices and computed a neural network. It seems to work (training set 50%), however I am not an expert in machine learning so my solution is most likely not good!
So my questions are:

Has anybody allready computed a neural network for the problem above and is willing to share his data?
Do you know similiar problems accessible for high school students which are better suited for this occasion?

For high school kids, I think the most important goal is to make sure they're impressed by what they've accomplished. To do that the task needs to be inherently useful. Classic things like the XOR problem or pixel counting aren't going to do the trick, because you're relying on the students to connect the dots and realize that this means you can build it into something cool. You need them to build a system

that does something cool,
which can't easily be accomplished with a handbuilt algorithm,
that seems to behave intelligently.

A few ideas:

Make an environment where agents play a game. Something like tic-tac-toe or rock-paper-scissors is probably best. At the end of the course, you can let the agents that the students have made battle each other in a tournament.
Create a simple a-life environment with 2D creatures with simple sensors and joints. Let students create the neural network for the creatures, so they learn to walk. You can also let them evolve the network topology when creatures mate.
A car driver. Again, this is best with an artificial environment, but you can probably get a dataset somewhere too. This is an example from Tom Mitchell's machine learning where they did this with an actual car and a human driver for the network to learn from.


Lower Bounds for Size of Independent Set in a Graph? I recently learnt that for any instance of a k-SAT problem with $m$ clauses and $n$ literals , we have an assignment of literals such that at least $m(1 - 2^{-k})$ clauses are satisfied.

I was wondering if we can we show a (non trivial) lower bound of the kind that any graph $G = (V,E)$ has an independent set of size $S$ where $S$ is some function in the number of vertices and edges or the like?

Since in the optimisation version we try to find a maximum independent subset, the tighter the lower bound, the better. Hence I was wondering if there is such a lower bound exists, how tight can we make it?

The relevant result is known as Turán's theorem. It states that if a graph has less than (roughly) $n(n-1)/(2r)$ edges then it has an independent set of size $r+1$, and this is tight.


Decidability problem solved by an alogrithm step by step difference between Decision and decidable problem How Decision procedure and Decidable problem are different from each other?
Both are having solutions in yes and no form. Is any else solution for both?

A decision problem is a problem of the form "Is my input in this set?", with a yes/no answer. A decidable problem is a decision problem that can be solved by a Turing machine.


Operation with second-order logic formulas I have one or more second-order logic formulas that correct for some finity model. What operation can I perform on them, so that resault is also correct for some finity model?

Just conjunction is impossible, example:
$x$ has finity model, $\lnot x$ has finity model, but $x \wedge \lnot x$ has not finity model. Are there any restriction?

Out of the standard logical operations ($\lor$, $\land$, $\neg$, $\implies$), the only ones that meet your conditions are $\lor$ and $\implies$.


Are entities in a many-to-many relation related individually? I know in some many-to-many relationships, an entity is related to other entities on an individual basis. But is this always the case?

For example, in the Authorship relationship between authors and books. An author can write many books, and a book can have many authors. In each such connection, an author is individually connected to the book he/she authors, and vice versa, a book is individually connected to its authors.

However, in some cases, a group of things relate to another group of things. The relationship seems to be between the groups of entities rather than individual entities.

For example in the picture below, one road is drawn as two segments i1 i2 in one map, and three segments j1, j2, j3 in the other map. In a sense, the two groups of segments form a one-to-one correspondence.

But does this situation constitutes a many-to-many correspondence in relational database theory?

If yes, this is weird, because unlike the authorship relationship, i1 seems to have nothing to do with j3 individually.

If not a many-to-many relationship, what is this kind of correspondence in relational database theory called? And how do we translate this to physical table design?

As far as I could understand, there are 3 entities here.

Map
Road
Road Segment

And the relationships between them are:

Map M:N Road
Road 1:N Road Segment
Map 1:N Road Segment

A map could have multiple roads and a road could in multiple maps. A road could have multiple segments, in each map it is a part of. And a road segment would be related to one map and one road.

And to identify whether two segments are related to same road we can query the Road Segment entity to get which segments are related to same roadId.


First Order Logic : Predicates I have a small problem with the first order logic, in particular, predicate logic

Let us take this sentence as an example:

Each teacher has given a form to each student.

From this sentence, can we have different reading?

This is my try to solve such problem, I did not know if this is the answer for such question:

Every Teacher has given a form to each Student.

(∀x)Teacher(x)^(∀y)  Student(y)^(∃z)Form(z)^Give(x,y,z)

If X is a Student then he has received a form from a teacher

Student(x)→(∃y)  Teacher(y)^(∃z)Form(z)^Give(x,y,z)

If X is a Teacher then he has gave a from for all his students

Teacher(x)→(∀y)  Student(y)^(∃z)Form(z)^Give(x,y,z)

If X is a form then a teacher gave it to all student.

Form(x)→(∀y)  Employer(y)^(∃z)Teacher(z)^Give(x,y,z)

EDIT

To clarify my needs !

I think that the form is in logical dependency, either of student, either of teacher, or both, so we can find three other readings; so What are those reading? (Look at the begining to find what I did)

And How can I transform this sentence in predicate logic?

Each teacher has given a form to each student.

because it seems that

(∀x)Teacher(x)^(∀y)  Student(y)^(∃z)Form(z)^Give(x,y,z)

is wrong.

Each teacher has given a form to each student.

becomes

$$\forall x\forall y[\mathrm{Teacher}(x)\wedge\mathrm{Student}(y)\to\exists z(\mathrm{Form}(z)\wedge\mathrm{Give}(x,y,z))]$$
The main thing is to understand this table:

$\begin{eqnarray*}\text{every } A\quad & \forall x(A(x)\to\dots) \\ \text{some } A\quad & \exists x(A(x)\wedge\dots) \end{eqnarray*}$


what does term "emit" in compiler mean? In lots of textbooks and papers, authors often state: compiler emits ...

I want to know why they prefer to use emit? (not return, not produce)

Does this have anything to do with the emitter of a compiler?

thanks

It is mostly used in the sense of "writing instructions to the program being built". Note that what is being "emitted" might still be massaged before ending up in the compiler output.


What is the time complexity of a linear search performed using 2 pointers? For an array, I'm using a left pointer (pointing to 0) and a right pointer (pointing to end).
For every iteration, if my search element is not found, I increment left and decrement right.
This iteration continues until left <= right. Find the code snippet below
left = 0
right = length - 1

while left <= right:
    // search logic
    left += 1
    right -= 1

What will be worst the time complexity of this algorithm?
Also, is this a type of linear search?

$O(n)$, since you still will go through the entire array.
And yes, this is a linear search since $O(n)$ is linear.


4-bit input, 5-bit output, logical right shift by 2, which is the correct set of 5 output bits? Suppose I have the following inputs:

1110
1111

If I perform a logical right shift by 2 on each, are the 5-bit outputs these:

00111
00111

or these:

01110
01111

If it's neither, then I'd appreciate an explain why and what I've done wrong!

There are two ways to do a shift: either the "new"  digit (the leftmost, msb) is set to zero, or it is set to the digit that was there before. The former is usually called logical shift while the latter preserves the sign of the number (in case you use the complement representation) and is called arithmetic shift. But sometimes both are just called shift, and one needs to clarify the desired behavior.

Since you as about buffers of length 5 bits, the msb is anyway 0 so logical shift-arithmetic shift, and I'd say the 2-bit right shift is:

01110  -> 00111 -> 00011
01111  -> 00111 -> 00011


Bounding rectangle of a line [Input]: the begin and end points of an arbitrary line (small red points) and the line width (green line)
[Example]: begin=(20,20), end=(100,50), width=5

[Output]: The set of pixels (not the total area) that are in the yellow rectangle
[Example]: {(20,20), (20,21), (20,22),...etc.}

How can i calculate the output set?

An algorithm to know if a point $P$ is in the rectangle $ABCD$ is to check that

$\vec{AB}\cdot \vec{AP}\leq 0$,
$\vec{DC}\cdot \vec{DP}\geq 0$,
$\vec{DA}\cdot \vec{DP}\leq 0$, and
$\vec{CB}\cdot \vec{CP}\geq 0$.

Since you have the two extremity point and the width $A,B,C$ and $D$ should be easy to compute. And you can restrict the point you are checking to $(x,y)$ such that $min(A_x,B_x,C_x,D_x)\leq x \leq max(A_x,B_x,C_x,D_x)$ and $min(A_y,B_y,C_y,D_y)\leq y \leq max(A_y,B_y,C_y,D_y)$.

It may not be optimal but it should be working.

Ps: I agree with @Dukeling.

[Edit] to compute $A$

If begin and end have the same abscissa (or ordinate) then it easy. Otherwise:

Let $begin=(b_x,b_y)$, $end=(e_x,e_y)$, $A=(x,y)$ and $width/2=w$ you know that:
$$\vec{beginend}=((e_x-b_x),(e_y-b_y))$$
$$\vec{beginA}=((x-b_x),(y-b_y))$$
hence:
$$\vec{beginend}\cdot\vec{beginA}=(e_x-b_x)(x-b_x)+(e_y-b_y)(y-b_y)=0$$
hence:
$$ x = b_x -\frac{(e_y-b_y)(y-b_y)}{(e_x-b_x)} $$
Also $|\vec{beginA}|=w$ hence:
$$(x-b_x)^2+(y-b_y)^2=w$$
hence:
$$(b_x -\frac{(e_y-b_y)(y-b_y)}{(e_x-b_x)}-b_x)^2+(y-b_y)^2=w$$
Solve this equation and you have $y$, then replace the solution in $$ x = b_x -\frac{(e_y-b_y)(y-b_y)}{(e_x-b_x)} $$ and you have $x$.

Notice that you have two solution one for $A$ the other for $D$ ...

Do the same for $B$ and $C$ with appropriate vectors.


RISC machines have register renaming? I know that one of the techniques used by RISC machines to improve the pipeline is the delayed branch, but what other techniques do they employ, namely, can they use register renaming?

I know that Superscalar processors have register renaming, but a Superscalar processor can only be a CISC machine, right?

RISC machines can have register renaming, just like CISC machines can have register renaming. Register renaming is an aspect of the processor implementation, whereas RISC is an aspect of the instruction set, so they are fairly orthogonal: there can be two processors implementing the same architecture (i.e. accepting the same code), but in different ways (and with different performance characteristics), one with register renaming and one without.

The Wikipedia article gives the example of the Alpha 21264. Alpha is pretty strongly on the RISC side.

The Alpha 21264 is considered superscalar, by the way. I don't know why a superscalar processor would have to be CISC or RISC: again, the ability to process multiple instructions in parallel is orthogonal to the complexity of the instruction set. In fact, RISC processors are more likely to be able to parallelize instruction execution successfully, because the instructions are easier to analyze. But CISC processors can and do do it too.


$NP \ vs \ co-NP$: tautology to SAT and vice versa? Let define formula $\Phi%$ given in CNF and it's complement $\overline \Phi$.

$\Phi$ is satisfiable iff $\overline \Phi$ is not tautology and vice versa.

$\Phi$ can be converted to $\overline \Phi$ in polynomial time using following method:

Change all literals with non-literals and vice versa: $\forall i:x_i \Rightarrow \overline {x_i}; \ \overline {x_i} \Rightarrow x_i$.
Change all disjunctions with conjunctions and vice versa.

This property is a corollary of CNF/DNF definitions.

This will give us a DNF $\ \overline \Phi\ $ of the same length as $\ \Phi$.

Assuming DIMACS format SAT solver can solve tautology this way:

Multiply all variables by $-1$.
Solve SAT.
Return $\overline {answer}$, where $answer$ is global (final) answer for SAT.

Example 1:

$\Phi = (x \lor y \lor \overline z) \land (\overline x \lor t) \land (\overline y \lor \overline t) = 1100.1010.0101.0000$ - is satisfiable.

$\overline \Phi = (\overline x \land \overline y \land z) \lor (x \land \overline t) \lor (y \land t) = 0011.0101.1010.1111$ - is not tautology.

Example 2:

$\Phi = (x \lor y) \land (\overline x \lor y) \land (\overline x \lor \overline y) \land (x \lor \overline y)= 0000$ - is not satisfiable.

$\overline \Phi = (\overline x \land \overline y) \lor (x \land \overline y) \lor (x \land y) \lor (\overline x \land y) = 1111$ - is tautology.

Does this proves that $NP = co-NP$? Or, maybe, somewhere I'm wrong with complexity classes?

Your algorithm doesn't prove NP = co-NP because you're using a Cook reduction to go from DNF-TAUTOLOGIES to CNF-SAT.  NP and co-NP aren't separate complexity classes under Cook reductions, they are separate under Karp reductions.  Under Karp reduction, changing the output of Turing machine after you've performed the polynomial-time transformation is specifically disallowed.

So while your algorithm is a way to use a SAT solver to validate proofs, it doesn't say anything about whether NP = co-NP.


Is this algorithm bubble sort or selection sort? #include <iostream>

int main() {
    int arr[10]{10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    for (int i = 0; i < 10; i++) {
        for (int j = 0;  j < 9; j++) {
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
            }
        }
    }
    // now the array is sorted!

    return 0;
}

I've just studied bubble sort and tried to implement that in c++ as the code above.

I've taught my friend the algorithm, but he implemented it as the following code, which worked and sorted the array, but I don't know what the name of algorithm he used. Here is a sample of what he used:

#include <iostream>

int main() {
    int arr[10]{10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    for (int i = 0; i < 10; i++) {
        for (int j = i + 1;  j < 10; j++) {
            if (arr[i] > arr[j]) {
                std::swap(arr[i], arr[j]);
            }
        }
    }
    // now the array is sorted!
    return 0;
}

Is this selection sort?

Yes, the code written by your friend implements the selection sort. It is not exactly how the selection sort is usually implemented, though.

What is done in your friend's code?

At the first iteration where i=0, it finds the smallest element by comparing the element at index 0 with all other element, swapping if necessary so that the minimum element so far will stay at index 0.

At the end of this iteration, the smallest element is at index 0.
At the next iteration where i=1, it finds the next smallest element by comparing the element at index 1 with all other element except the smallest element, swapping if necessary so that the next smallest so far stays at index 0.

At the end of this iteration, the smallest and second smallest element is at index 0 and 1, respectively.
At the next iteration where i=2, it finds the next smallest elements by comparing the element at index 2 with all other element except the smallest element, swapping if necessary so that the next smallest so far stays at index 2.

At the end of this iteration, the first 3 smallest elements are sorted at index 0, 1 and 2.
And so on.
Finally, at the beginning of last iteration where i=9, the first 9 smallest elements are sorted at first 9 indices. The 10th smallest elements, which is also the largest element in this 10-element array, must have been at the last index.

So the sorting is done.

Your friend implements the selection sort.

Let us check what is selection sort. According to the Wikipedia article, here is the idea of selection sort.

  The algorithm divides the input list into two parts: the sublist of items already sorted, which is built up from left to right at the front (left) of the list, and the sublist of items remaining to be sorted that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.

We can verify that your friend's code implements exactly that idea above. In fact, if you replace int arr[10]{10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; with int arr[5]= {11, 25, 12, 22, 64};, updating the bounds accordingly, your friend's code will produce exactly the same sublists at end of each outer loop as shown in the example in Wikipedia.

Your friends' code is different from how the selection sort is usually implemented. The common implementation uses an index iMin to track the minimal element while your friend uses the element at the expected location to track the minimal element.

Your friend's code runs slower than the usual implementation because it uses much more swaps in average although both implementation uses exactly the same number of comparisons, $n(n-1)/2$. On the other hand, it uses no more swaps than a bubble sort.

Your friend's code is simpler to write and ends up even shorter than the common implementation, supporting the claim "selection sort is noted for its simplicity".

You may want to enjoy visualization of various sorting algorithms at Topal.com.

Exercise

If arr[j] > arr[j + 1] in your code is changed to arr[j] < arr[j + 1], what is the result? Does it implement bubble sort still?
If arr[i] > arr[j] in your friend's code is changed to arr[i] < arr[j], what is the result? Does it implement selection sort still?

Show that your friend's code uses no more swaps than a bubble sort. Give an example when your friend's code uses less swap than a bubble sort.


Are finite-domain binary constraint satisfaction problems solvable in polynomial time? Suppose a CSP has $n$ variables with finite domains of maximal size $d$. Furthermore, all constraints on the variables are binary. Can such a CSP be solved in polynomial time in $n$ and $d$?

This was an exam question on last year’s AI exam, but I’m not sure how to solve it.

I know the problem of graph coloring is easily reduced to such a binary CSP, so solving them is NP-complete. Thus, I’m pretty sure that there is no known polynomial-time algorithm. Can I prove that there isn’t one?

I don't know, but if you manage, make sure to let us know.

The reduction seems easy indeed, with $d$ mapping to the number of colors and each constraint to an edge.

However, a polynomial-time algorithm for any $\mathcal{NP}$-complete problem exists if and only if $\mathcal{P} =\mathcal{NP}$; doing what you ask would imply $\mathcal{P} \neq \mathcal{NP}$.


Which of the following sequences could not be the sequences of nodes examined in a binary search tree? Suppose that we have numbers between $1$ and $1000$ in a binary search tree and want to search for the number $363$. Which of the following sequences could not be the sequences of nodes examined

a) 924,220,911,244,898,258,362,363$

b) 925,202,911,240,912,245,363

c) 2,399,387,219,266,382,381,278,363

d) 935,278,347,621,299,392,358,363

e) 925, 202, 911, 240, 912, 245, 363

I know that $d$ and $e$ are not valid sequences, my professor told us so. I know it has something to do the range between jumping from node to node, which has something to do with the following property of BST's

Let $x$ be a node in a binary search tree. If $y$ is a node in the left subtree
of $x$, then $y.key \leq x.key$. If $y$ is a node in the right subtree of $x$, then $y.key \geq x.key$.

I just don't see it, been trying to simulate the path sequence with no clear breakthrough.

Actually the test is quite easy. If you consider the subsequence of numbers greater than the final number $363$, this sequence is supposed to decrease.

Thus, in the case of $e: 925, 202, 911, 240, 912, 245, 363$, the subsequence is $925, 911, 912, 363$ and we see the problem.

Why is that so? If we see a number $x$ larger than the target $363$, we are supposed to move to the left subtree of $x$ where all numbers will be smaller than $x$. Thus also all numbers we will see from there will be smaller. As a consequence the numbers larger than $363$ will decrease.

Similarly, the numbers smaller than $363$ will increase. That is why $d$ fails: $278,347,299,358,363$.


Prove that a set A is semi-decidable if and only if there is a polynomial time relation R(x,y) I know if there is a decidable relation R(x,y) for x in A, then A is semi-decidable. But how can I prove the relation is polynomial time?

For R(x,y), x is  where M is a TM, y is the accepting configuration of M. Is this a polynomial-time relation?

For $R(x,y)$, $x$ is where $M$ is a TM, $y$ is the accepting configuration of $M$. Is this a polynomial-time relation?

Yes that is the right idea. Except $y$ should be a sequence of configurations that starts in the initial configuration and ends in the accepting configuration.

To see why this works, we have to consider the running time of the TM that accepts $R(x, y)$. First the TM looks at the input $x$, and then it looks at the sequence of configurations $y$. The sequence of configurations looks something like a table:

Tape at time 0: x1 x2 x3 .... xn 0 0 0 0 0 .... 0
                ^HEAD, state q0
Tape at time 1: x1 x2 x3 .... xn 0 0 0 0 0 .... 0
                   ^HEAD, state q1
Tape at time 2: x1  1 x3 .... xn 0 0 0 0 0 .... 0
                       ^HEAD, state q2
...

and so on. So how does our TM check if this is in $R(x, y)$? We should check to make sure that the initial configuration has $x$ on the tape. How long will this take? And then we should check that $y$ is a valid sequence of configurations of according to the transition behavior of $M$. How long will that take? Finally, we need to check that the last configuration in $y$ is accepting. How long will that take?


Runtime-Analysis for single loop incremented by a factor of 3 So, I'm trying to understand how to  get the run time of this loop:

for(int i = 1; i < n*n*n; i*=3) {...}

So, far I know:

loop starts at 1
finishes when $i  > n^3-1$
that $i$ is multiplied by 3 each iteration.

Intuitively it seems like as $n$ gets larger the number of iterations decreases which makes me think that the run-time is $O(log$ $n)$. My question is if this is correct if it is what is a mathematical way I could derive that answer?

That's right. This for loop stops when:
$$
3^i < n^3 \rightarrow i<3\log(n)
$$
Which implies the complexity of this for loop is $O(\log(n))$.


Counting arrays with Euclidean distance at most 2 from a given binary array I have a binary array like this:

$$A = [0,1,0,0,1,0]\,.$$

I'm trying to find a way to calculate how many arrays of the same length exist that have a Euclidean distance of 2 or less from this array.

So, how many arrays of length 6 exist where

$$\sqrt{\Sigma(A_{_i} - B_{_i})^2}\leq 2\,?$$

I'm trying to find or create a formula that takes an array like above and outputs a count of how many possible binary arrays exist that fit the conditions of the above formula.

I've looked online for a formula without success.

Don't search for a formula – you'll probably never find something so specific. Instead, try to break up the task into smaller units.

Since your arrays are binary,
$$(A_i-B_i)^2 = \begin{cases}0 &\text{if }A_i=B_i\\ 1&\text{if }A_i\neq B_i\,.\end{cases}$$

So $\sqrt{\sum(A_i-B_i)^2}\leq 2$ if, and only if there are at most four values of $i$ such that $A_i\neq B_i$.  So you just need to compute the number of ways that $B$ could have zero, one, two, three or four different entries from $A$ (or, more simply, the number of ways that it could have five or six different entries, and subtract that from the total possible values of $B$). This calculation is high-school combinatorics. Note that, because the arrays are binary, there's only one value of $B_i$ that's the same as $A_i$ and only one that's different.


Implicit nil checks in algorithms I am reading algorithms in a CS book where a potentially nil value is passed to a function, but neither the caller nor the callee check if the value is nil. Is this a common practice in algorithms?

To be more precise, I am implementing a red-black tree and the grandparent of a node is passed to a rotation function, but if correctly understand the algorithm, the grandparent might be nil at the time the rotation function is called.

I should probably warp such calls into a conditional block, but I was curious to know if this is common for algorithms to be specified that way, and if there are any additional advices on how to handle those cases.

Thank you

The concept of a nil pointer is an implementation detail which is programming language specific. In some implementations, an attempt to accept the grandparent when there is none will just trigger an exception. This hints that the algorithm designer should not worry about nil pointers.

Indeed, in your example, the rotation function should simply not be called on a node with no grandparent. If you use the data structure correctly, then this will simply not happen. There are only two cases in which you would try to rotate a node without grandparent:

Implementation bug. You haven't coded the algorithm correctly.
Non-conforming usage. Your program for some reason calls the rotation procedure directly.

If your program is correct and it is used according to the interface of the data structure, then you will never attempt to rotate a node without a grandparent. Therefore if your code is attempting to dereference a nil pointer, you can be sure that there is some bug in your code. During development, you should probably raise an exception. For production code, you should follow whatever convention you do in any other part of your code.


Meaning of 'running time is $O(n^2)$' I have a question from Introduction to Algorithms by CLRS,

When we say "the running time is $O(n^2),$" we mean that there is a function $f(n)$ that is $O(n^2)$ such that for any values of $n$, no matter what particular input of size $n$ is chosen, the running time on the input is bounded from above by the value of $f(n)$.

What do the authors mean by saying there exists a function that is $O(n^2)$? Do they mean that this function is from the set $O(n^2)$? Is the last part which I highlighted correct? I think it must be "... from above by $O(n^2)$." I appreciate your answers.

We say that a function $f(n)$ is $O(n^2)$ if there exist constants $C,N>0$ such that $f(n) \leq Cn^2$ for all $n \geq N$. We usually denote "$f(n)$ is $O(n^2)$" by "$f(n) = O(n^2)$".
An algorithm has running time $O(n^2)$ if its worst-case running time is $O(n^2)$. That is, if we denote by $T(n)$ the maximum running time of the algorithm on inputs of length $n$, then the algorithm has running time $O(n^2)$ if $T(n) = O(n^2)$.
Equivalently (and this is the point of the CLRS formulation), an algorithm has running time $O(n^2)$ if there exists some function $f(n) = O(n^2)$ such that the running time of the algorithm on an input of length $n$ is always at most $f(n)$.
If we denote the running time of the algorithm on the input $x$ by $T(x)$, and the length of $x$ by $|x|$, then we can see the difference between these two equivalent definitions by writing them out formally.
The first definition is
$$
\max_{|x| = n} T(x) = O(n^2),
$$
where the left-hand side defines a function of $n$, which we denoted above by $T(n)$.
The second definition states that for some $f(n) = O(n^2)$,
$$
T(x) \leq f(|x|).
$$
If the second definition holds, then in particular
$$
\max_{|x|=n} T(x) \leq f(n),
$$
and so
$$
\max_{|x|=n} T(x) = O(n^2),
$$
which is the first definition.
If the first definition holds, then we can take $f(n) = \max_{|x|=n} T(x)$ to obtain a function satisfying the second definition:
$$
T(x) \leq \max_{|y|=|x|} T(y) = f(|x|),
$$
where the first definition guarantees that $f(n) = O(n^2)$.


Parallel merge sort using hypercube connection template I've been reading about hypercube connection template for parallel algorithms. The general scheme is explained in Designing and Building Parallel Programs by Ian Foster and it's pretty clear.

What I don't understand is how it's applied on the merge sort in §11.4 The point I'm most interested is the parallel_merge function in the pseudocode, i.e. parallel merge algorithm.

The point I'm most interested is the parallel_merge function in the pseudocode, i.e. parallel merge algorithm.

procedure parallel_mergesort(myid, d, data, newdata)
begin
  data = sequential_mergesort(data)
  for dim = 1 to d
    data = parallel_merge(myid, dim, data)
  endfor
  newdata = data
end

Please, explain to me step by step, assuming we have an array of twelve elements $(3,1,5,7,4,2,8,9,4,2,7,5)$ and we've broken this data to four processors like this:

$\qquad ((3,1,5),(7,4,2),(8,9,4),(2,7,5))$.

What data will have each process after each iteration? I understand why we use the hybercube template in this algorithm, but why do we have exactly $i$ compare-exchanges at the $i$-th level? I mean, when $i=1$, we compare-exchange data from processes $1-2, 3-4, .. P-1, P$. That's not $1$, that's $P/2$? Do I misunderstand something?

They write

  The $i$-th parallel merge takes two sequences, each distributed over $2^{i-1}$ tasks, and generates a sorted sequence distributed over $2^i$ tasks.

For $i=1$, that reads

  The first parallel merge takes two sequences, each stored locally on one task, and generates a sorted sequence distributed over two tasks.

That is, every node performs one compare-merge. Similarly, for higher $i$, each node performs $i$ such operations.

They use it to derive "per-processor communication cost" $T_{comm}$ which clarifies that they do indeed count processor-wise in the prequel. That makes sense, too: communication happens in parallel, so in order to derive bounds on overall runtime you can bound every (abstract) step from above with the longest processing time found among all processors in that step.


Are depth-first/breadth-first considered special cases of best-first? In literature in general, are DFS and BFS considered to be special cases of best-first search?

Suppose the cost function is:

$f(n) = g(n) + h(n)$

Is it correct to reason that if and $g(n) = depth(n)$, then

If $\forall_n h(n) = 0$, we have a breadth-first search

If $h(n) = i$, where i is the number of nodes visited before visiting, we have depth-first search.

?

Are depth-first and breadth-first search usually considered special cases of best-first search?

The answer to your question is, in both cases, No.

The reason is as follows: Both depth-first search and breadth-first search are uninformed search algorithms. A distinctive feature of these algorithms is that they stop once the goal node is generated.

Now, if all operators are given the same cost (so that you consider them to have the same cost equal to 1), then:

Breadth-first search is guaranteed to find the solution, and also to deliver an optimal one. This is, it is both complete and admissible (some people refer to this also as been optimal).
Depth-first search, however, is neither complete nor admissible because it is bounded by a maximum depth. It might well happen that the goal lies beyond it and thus, it cannot guarantee to find it.

Best-First search, on the other hand, uses an OPEN list where nodes are sorted in increasing order of $f(n)=g(n)+h(n)$ where: $g(n)$ is the cost of the current path from the start node to node $n$, and $h(n)$ is an estimate of the remaining effort to reach the goal from $n$. As such, $f(n)$ stands for an estimate of the best path from the start node to the goal that goes through node $n$. However, in contrast with the case of uninformed search algorithms, Best-first search algorithms halt only when the solution is about to be expanded! This makes a lot of sense. Under a number of assumptions (such as admissibility of the heuristic function), sorting nodes in ascending order guarantees that the true cost is above the estimation given by $f(n)$, so that only when expanding a goal you can ensure that all the other nodes stand for potential solutions with a cost greater or equal than the cost of the current solution.

Therefore, from your definitions of $f(n)$ (and assuming unit costs):

Making $f(n)=\mathrm{depth}(n)$ would result in an algorithm that expands nodes in the same order than a breadth-first search algorithm (up to tie-breaking). In addition, it will expand more nodes than it since after generating the goal, it has to expand all nodes in the current level before expanding the goal ---in the next level.
Your second choice, $f(n)=\mathrm{depth}(n) + i$, with $i$ been "the number of nodes visited before visiting" is rather confusing to me. I do not know what you might mean by "visited before visiting". In spite of it, however, note that a Best-First search algorithm would proceed further after generating the goal node much the same.

Your question makes a lot of sense. In case you want to access additional material related to it, please refer to Robert C. Holte. Common Misconceptions Concerning Heuristic Search". Symposium on Combinatorial Search SoCS 2010. Pages 46--51. See, specifically, the bottom of the left column in page 49.

Hope this helps,


How does the forget layer of an LSTM work? Can someone explain the mathematical intuition behind the forget layer of an LSTM?

So as far as I understand it, the cell state is essentially long term memory embedding (correct me if I'm wrong), but I'm also assuming it's a matrix. Then the forget vector is calculated by concatenating the previous hidden state and the current input and adding the bias to it, then putting that through a sigmoid function that outputs a vector then that gets multiplied by the cell state matrix.

How does a concatenation of the hidden state of the previous input and the current input with the bias help with what to forget?

Why is the previous hidden state, current input and the bias put into a sigmoid function? Is there some special characteristic of a sigmoid that creates a vector of important embeddings?

I'd really like to understand the theory behind calculating the cell states and hidden states. Most people just tell me to treat it like a black box, but I think that, in order to have a successful application of LSTMs to a problem, I need to know what's going on under the hood. If anyone has any resources that are good for learning the theory behind why cell state and hidden state calculation extract key features in short and long term memory I'd love to read it.

Think of it like this: The cell state $h_t$ is a vector.  The forget vector $f_t$ is used to choose which parts of the cell state to "forget".  We update the hidden state with something like $c_t = f_t \circ c_{t-1}$ (it's actually more complicated, but let's start with that, to gain intuition).  Suppose $f_t$ were a vector of 0's and 1's.  In the coordinates where $f_t$ is 1, the value of $c_{t-1}$ would be copied over to $c_t$ (it's not forgotten).  In the coordinates where $f_t$ is 1, $c_t$ is reset to zero and the value of $c_{t-1}$ is ignored  (it's forgotten).  So, the forget vector can be used to control in which positions we forget values from the previous cell state vector.

Now what remains is to figure out a way to choose a forget vector $f_t$.  In general we might want to choose which positions to forget based on both the current input $x_t$ and the previous hidden state $h_{t-1}$.  So, we should compute $f_t$ as some function of $x_t$ and $h_{t-1}$.  Many choices of how to represent that function might be possible, but a LSTM chooses a specific function for this.  In a LSTM, this is done by a single-layer fully-connected neural network.  A single-layer fully-connected neural network concatenates all of the inputs, then multiplies them by a matrix, adds a bias, and feeds the result to an activation layer (in this case, sigmoid activation).  So that's why the formula for $f_t$ looks the way it does: that formula is capturing what a single-layer fully-connected neural network does.


What is the most efficient way to find bSmooth values in QS? The heaviest part of QS is to search for bSmooth numbers.
So far I thought about two algorithms for solving this.

Trial division

calculate $X$ as a product of all the values in the factor base
speed up the trial division with $gcd(X,Y)$ where $Y$ is a potential bSmooth value

The most efficient method is to use a sieve; this is why the method is called the quadratic sieve. It should be mentioned, though, that the sieve is just an optimization over Dixon's method, and doesn't affect the asymptotic running time apart from some (multiplicative) lower order terms. For a description of the sieve, you can start with Wikipedia.


Students in classroom problem - Flow in network I have room, which is opened some days in week, in different hours each day.

I have multiple students, each has time some days in week, in different hours.

Each student have to visit the room exactly once in the week, for exactly 50 minutes.

Room is unusable for 20 minutes after 2nd student the day, it means, that after the 2nd student have to be at least 20 minute break before 3rd. So something like this:
7:00-7:50
7:50-8:40
(20 mimutes break)
9:00-9:50
There is no break after 4th, 6th, ... student. Only after 2nd one.

How can I find best solution to this? I want to position all (or the most I can) students.

I've thought of using flow in network (see image). Groups (G1, G2, ...) group times (7:00, 7:05, ...) that are within 50 minutes of each other. Pairing student (S1, S2) with time would instantly disable any groups, that contains the time. But that would require to flow going IN->Student->Time-> to split into multiple groups ->Group1+Group2->OUT. How can I achieve this? How should I modify maximum flow search algorithms to do so?

Or is there better way how to do what I'm trying to accomplish?

The best way I can see to solve this is with integer linear programming.  This is not a polynomial-time algorithm, but it might work well enough in practice.  (I don't think network flow algorithms will work here.)

In particular, you introduce zero-or-one variables $x_{i,t}$, with the intent that $x_{i,t}=1$ means that student $i$ is scheduled in the room starting at time $t$, or $x_{i,t}=0$ otherwise.  Then you add inequalities to ensure that these meet all of your requirements:

$\sum_t x_{i,t} = 1$: each student is scheduled at a single time.
$x_{i,t} + x_{j,t'} \le 1$ whenever $i \ne j$ and $t,t'$ are within 50 minutes of each other: no two students may be scheduled at an overlapping time.

Then you feed this to an off-the-shelf ILP solver and ask it for a feasible solution.  The result is a valid schedule.

As described above, I have ignored the requirement about the 2nd student of the day.  You can fix this by adding some extra variables and inequalities.  Let $y_{i,t}=1$ if student $i$ is assigned at time $t$ and is the first student assigned that day, and $z_{i,t}=1$ if student $i$ is assigned at time $t$ and is the second student assigned that day.  Then we have additional constraints:

$y_{i,t} \le x_{i,t}$, $y_{i,t} + \sum_j \sum_{t' < t} x_{j,t'} \le 1$, $x_{i,t} - \sum_j \sum_{t' < t} x_{j,t'} \le y_{i,t}$, and $\sum_i \sum_{t \in D_k} y_{i,t} = 1$ where the last sum is over all $t$ that fall on day $k$ (on the same day).  These ensure that the $y$'s are consistent with the $x$'s.
$z_{i,t} \le x_{i,t}$, $z_{i,t} \le \sum_j \sum_{t' < t} y_{j,t'}$, $x_{i,t} - 2 + \sum_j \sum_{t' < t} (x_{j,t'} - M z_{j,t'}) \le z_{i,t}$,  $\sum_i \sum_{t \in D_k} z_{i,t} = 1$ where the last sum is over all $t$ that fall on day $k$ (on the same day) and where $M$ is sufficiently large (e.g., at least the number of students).  These ensure that the $z$'s are consistent with the $x$'s.
$z_{i,t} + x_{j,t'} \le 1$ whenever $i\ne j$ and $t,t'$ are within 110 minutes of each other: this ensures a 20-minute gap after the second student of the day.

This should enforce the additional constraints.  Double-check the formulation; I haven't checked it carefully, and there might be small errors in what I wrote.  In general, Express boolean logic operations in zero-one integer linear programming (ILP) gives some helpful tips on encoding constraints into linear inequalities for ILP.


How Tarjan algorithm work for the 2-SAT Tarjan's algorithm for 2-SAT is based on the truth:

  a 2-CNF formula is satisfiable if and only if there is no variable that belongs to the same strongly connected component as its negation.

But I don't find any reason for the right to left direction. how can the inexistence of such variable guarantee satisfaction of CNF?

I tried to follow the steps of the algorithm, and I was stuck here:

  For each component in the reverse topological order, if its variables do not already have truth assignments, set all the literals in the component to be true. This also causes all of the literals in the complementary component to be set to false.

Isn't it possible the variable is already assigned WRONGLY? When we keep assigning TRUE from the back, and we assign the FALSE in the middle, but the TRUE is to be assigned to the next variable. In this case, the feasibility breaks.

Of course this kind of case never happens because the algorithm is right and many people use this algorithm well. But so many post says it as the trivial things.

I think the reason why those assignment is possible is relevant to the skew-symmetric condition of the graph, since (x -> ~x -> y -> ~y) never has true assignments.

a 2-CNF formula is satisfiable if and only if there is no variable that belongs to the same strongly connected component as its negation.
But I don't find any reason for the right to left direction. how can the inexistence of such variable guarantee satisfaction of CNF?

Think of a variable assignment for some unsatisfiable 2-SAT instance.  This means one or more clauses must remain unsatisfied whatever the assignment.  You change the setting of one or more variables to satisfy those clauses, but this unavoidably leaves some new clause or clauses unsatisfied because the instance is unsatisfiable.  The failure of your change to satisfy the instance implies that some other variable's value must change.  You repeat the procedure again and again, changing other variables as implication demands, but never succeed in satisfying all the clauses.  Eventually, because the number of variables is finite, a failure implies that you change the value of a variable you've already visited... and that is your circular implication from $x$ to $\bar{x}$ back to $x$.  Without a circular implication you will eventually reach the end of the implication chain and have a satisfying assignment.  The only way not to reach the end of the chain is for the chain to be circular between a variable and its negation.


Let $L_4$ $\subseteq$ {0,1}$^*$ be the set of all palindromes whose first character is 1. Give a context-free grammar for $L_4$ Let $L_4$ $\subseteq$ {0,1}$^*$ be the set of all palindromes whose first character is 1. Give a context-free grammar for $L_4$.

I just wanted to check if my grammar is correct or not.

$$A \rightarrow 1B1$$
$$B \rightarrow 0B0\;|\;1B\;|\;0B\;|\;A\;|\;\epsilon$$

Not exactly, as your $1B$ and $0B$ productions might cause problems. You will accept 1101 for example. I believe just simplyfing it a bit, like this:

$A → 1B1\ |\ 1\ |\ \epsilon$

$B → 0B0\ |\ 1B1\ |\ 1\ |\ 0\ |\ \epsilon$

is enough (if we say that an empty string is a palindrome).


Finding a subset with few neighbors Given a bipartite graph $G(X+Y,E)$, how can I find a non-empty subset $Y'\subseteq Y$, such that $|N(Y')| \leq |Y'|$ (where $N$ is the set of neighbors)?

If $|Y|\geq |X|$ then the problem is easy - $Y'=Y$ satisfies the requirements. The interesting case is $|Y| < |X|$. In this case a solution might not exist, for example here:

$$
x_1 - y_1
\\
x_2 - y_1
$$

the only subset of $Y$ that satisfies the requirement is $\emptyset$. Is there an efficient algorithm for deciding whether a solution exists, and if so, find one?

A possible first step is to find a maximum matching in the graph. If its size is less than $|Y|$, then by Hall's theorem there exists a $Y'\subseteq Y$ with $|N(Y')|< |Y'|$, and it can be found efficiently, so we are done.

But if the size of the matching is $|Y|$, then... I am stuck.

RELATED PROBLEMS:

Finding a subset in bipartite graph violating Hall's condition: there, the problem is to find a subset with $|N(Y')|< |Y'|$; here, the problem is to find a non-empty subset with $|N(Y')|\leq |Y'|$.
In bipartite expansion, the goal is to find a subset $Y'$  containing a fraction $\beta$ of the vertices of $Y$ which minimizes the size of $N(Y')$. The problem is hard to approximate. However, our problem is possibly easier, since we  only require $Y'$ to be non-empty, and only require $|N(Y')|$ to be at most $|Y'|$ - we do not try to minimize it.
In union minimization, we are given a set-system and an integer $k$, and the goal is to find $k$ sets such that their union is minimized. We can view the set-system as a bipartite graph with sets on one side and elements on the other side; then, the goal is to find a $Y'$ of size $k$, such that $|N(Y')|$ is minimized. This is hard to approximate, but again our problem is potentially easier since it does not insist on $k$ and does not require minimization.

So, can the problem be solved in polynomial time?

I have an idea and will be happy to know if it is correct, or can be corrected.

Consider the integer linear program:

\begin{align}
\text{maximize} && \sum_{j\in Y} y_j - \sum_{i\in X} x_i
\\
\text{subject to} && y_j - x_i \leq 0 && \forall (i,j)\in E
\\
&& 0\leq x_i \leq 1,~~ 0\leq y_j \leq 1 && \forall i\in X, j\in Y
\\
&& x_i\in \mathbb{Z},~~ y_j\in\mathbb{Z} && \forall i\in X, j\in Y
\end{align}
In this program, there is a variable $x_i$ for each node $i$ in $X$, and a variable $y_j$ for each node $j$ in $Y$.
Let $X'$ be the subset of $X$ defined by $\{i\in X: x_i=1\}$, and $Y'$ the subset of $Y$ defined by  $\{j\in Y: y_j=1\}$.

The constraints $y_j - x_i \leq 0$ ensure that, if some vertex $j$ is in $Y'$, then all its neighbors are in $X'$, so $X'\supseteq N(Y')$.
The objective is to maximize the difference $|Y'|-|X'|$. If the optimal solution is at least 0, then $|Y'|\geq |X'| \geq |N(Y')|$, so $Y'$ is the required set. On the other hand, if the optimal solution is negative, there is no such set.

In general, integer linear programs are hard to solve. But in this case, the matrix of constraints is Totally unimodular. It satisfies the Hoffman-Gale conditions: every entry in the matrix is one of $+1, 0, -1$; every row in the matrix contains at most two nonzero entries; and if there are two nonzero entries, they have opposite signs. Therefore, we can solve the LP without the integrality constraints, and we are guaranteed to get an integral solution which gives us $Y'$.

The only problem is that the above LP does not guarantee that $Y'$ is non-empty. Adding a constraint such as $\sum_{j\in Y} y_j\geq 1$ would invalidate the argument of total-unimodularity. A possible solution is to solve $|Y|$ different linear programs: for each vertex $j\in Y$, solve the LP with the constraint $0\leq y_j \leq 1$ replaced with the constraint $y_j = 1$. If for some $j\in Y$ the objective is at least 0, we have found a non-empty $Y'$ as required. Otherwise, such $Y'$ does not exist.


Geometric intuition behind VC-dimension Recently, I learnt about VC-dimension and how its boundedness assures PAC learnability on uncountable range spaces (let's assume that hypothesis class is the same as the family of concepts we want to learn).

My question is simple: What is/are the geometric intuition(s) behind the concept of VC dimension?

The VC dimension is a complexity measure for a family of boolean functions over some domain $\mathcal{X}$. Families who allow "richer" behavior have a higher VC dimension. Since $\mathcal{X}$ can be arbitrary, there isn't a general geometric interpretation.

However, if you think of $\mathcal{X}$ as $\mathbb{R}^d$, then you can think of binary functions as manifolds, whose boundary is what's separating positive and negative labels. Families with more "complex" boundaries have a high VC dimension, whereas simple manifolds do not, e.g. the dimension of linear separators is $O(d)$, while convex polygons (with unbounded number of edges) have infinite VC dimension. The more complex you allow the boundary to be, the more likely it is that you can find a large set for which you can agree with any labeling, by avoiding the negative labels in a "snake like" shape.


How is the problem, {⟨G⟩|G has no triangle} in Logspace? I read this problem as a part of my course curriculum, in my professor's notes. I am not able to understand about the standard solution, that if I list all the possible triplets of vertices as 3-tuples in the tape, then how come my solution is limited to log-space?

As far as my understanding, listing all the 3-tuples in the tape would need $\binom{n}{3}$ combinations, and hence, $O(n^3)$ space.

I am not able to find the flaw in my understanding, grateful ever for the hint.

P.S. This reference is from our course slide:

  Let $L$ be the language $\{⟨G⟩ \: | \: G\text{ has no triangle}\}$. Then $L$ can be recognized in log-space as follows: On the work tape, the machine $M$ can write all 3-tuples of the vertices of $G$. For each tuple written, the machine checks if there is a triangle passing through those vertices. If all tests fail, then $M$ accepts, otherwise $M$ rejects. The space used by $M$ is enough to store three vertex identifiers, therefore $L$ is in log-space.

FOR x := 1 TO n DO
    FOR y := 1 TO n DO
        FOR z := 1 TO n DO
            IF E(x,y) && E(y,z) && E(z,x) THEN REJECT
ACCEPT

Each of the variables x, y and z requires $\Theta(\log \texttt{n})$ bits to store an integer between $1$ and $\texttt{n}$.


Weaknesses arising from using same key in both channel directions I came across the following question:
Which of the following risk may arise, when same key is used to encrypt both directions of a communication channel, that are not present if using different keys in both direction?
The answer to the question was reflection attack. The other options provided were denial of service, eavesdropping and none of the above.
I presume it could be eavesdropping. Eg: When a Diffie-Hellman key exchange is performed, a man-in-the-middle attack (type of eavesdropping attack) could occur.
So is the answer reflection attack or eavesdropping or something else entirely and why ? I tried looking up resources to justify and figure out the right answer but this is what I could conclude with.

Suppose that the keys used in both directions are the same. You listen to something sent from A to B:

kjhsdfiugdsa8ltr634o87qy5843jlgrwjklfjgsfds

You then listen to something sent from B to A:

jh35i798fdgkjh53jkh87gfhkjsfhtjk35h1o8798ug

Does it matter that the key is the same? Can you understand any of the messages?

If the answer to these questions is negative, then eavesdropping can be ruled out.

In contrast, suppose that you sent the following message from B to A:

kjhsdfiugdsa8ltr634o87qy5843jlgrwjklfjgsfds

You don't necessarily have any idea what this means, but it is identical to a message sent from A to B.

Because the key is the same, whatever meaning the original message had, so does this one.

This kind of attack (which is easy to thwart even if the keys are the same) is known as replay.


Minimum sum of squared Euclidean distance between two arrays Question:
Given two sorted sequences in increasing order, $X$ and $Y$. $Y$ is of size $k$ and $X$ is of size $m$.
I would like to find a subset of $X$, $i.e$, $X'$ of size $k$, and considering the following optimization problem:$$d(Y,X') = \sum_{j=1}^{k}(y_{j}-x'_{j})^{2}$$ And $X'$ is a subset of $X$ of size $k$, $y_{j} \text{ and } x'_{j}$ is element in $Y$ and $X'$. I would like to find the subset of $X$, to reach the minimum of $d(Y,X')$.
Note that $X'$ could have $k!$ numbers of arrangements, so its order is totally unknown.

What I have came up with so far:
I would like to approach it using Dynamic Programming, and I think I would first compute the squared distance between each element in $Y$ and $X$, but I'm having trouble in determining what is the subproblem and how to solve ths using DP. Thank you!
Update: The $X'$ could be sorted, which means we could aim at finding a sorted subset of $X$.

for m' = 0 to m
for k' = max(0, m-m') to min(m', k)
Take the problem of the first m' items of X and the first k' items of Y. Find the value of the smallest sum, and whether X[m'] is in that sum.
The optimal subset of the first m' items of X is either the best subset of the first m'-1 items of X matching the first k' items of Y, or the best subset of the first m'-1 items of X matching the first k'-1 items of Y, with X[m'] and Y[k'] added.
Note that sets and subsets are not sorted. If you want the indexes in arbitrary order, sorting X and Y first should work.


Show how a sentence can be produced from a grammar (Dragon book 2.1) In the Dragon book (Aho, Sethi, Ullmann) there is one exercise I don't get.

  Chapter 2, Exercies: 2.1
  Given the context-free grammar
  $$S \to S S + \mid S S * \mid a$$
  Task: Show how the signs aa+a* can be produced from this grammar.

I understand the grammar, $S$ can have the form $S S +$… and so on. But I don't know what I'm supposed to do in this task. Sadly I can't find any solutions on the web.

$$\begin{align*}
S \Rightarrow & SS* \\
  \Rightarrow & SS+S* & \text{(leftmost derivation )} \\
  \Rightarrow & aS+S* \\
  \Rightarrow & aa+S* \\
  \Rightarrow & aa+a* \\
\end{align*}$$