Karp hardness of digraph coloring without monochromatic dicycle Problem statement:

  Input: a digraph $G(V, A)$ and a natural number $k$

  Output: YES if it is possible to color all vertices of $V(G)$ by $k$ colors such that no directed cycle is monochromatic, NO otherwise

Is this an $NP$-complete problem?

Our problem is $\mathrm{NP}$-complete by a Karp reduction from $\mathrm{NAE}$-$\mathrm{3SAT}$

In fact, both the undirected and directed version are $\mathrm{NP}$-complete. First, we will describe the reduction for the undirected version. Then, we show how to orient all the edges of the undirected graph to obtain a digraph to finish the reduction for the directed version.

REDUCTION FOR UNDIRECTED VERSION

Given an instance of $\mathrm{NAE}$-$\mathrm{3SAT}$, we will construct an undirected graph such that there exists a solution for the $\mathrm{NAE}$-$\mathrm{3SAT}$ instance if and only if it is possible to color the vertices of this graph by $2$ colors such that no cycle is monochromatic.

For each clause $j$, create a $K_3$ cycle each vertex of which corresponds to one literal of clause $j$.

Now, for each pair of opposite literals (one positive and one negative literal of the same variable) $l_{jm}=x_i$ and $l_{kn}=\lnot x_i$, we connect them by a gadget as follows. (Here, $l_{ab}$ is literal $b$th of clause $a$, where $1\leq b\leq 3$)

The gadget to connect $l_{jm}$ and $l_{kn}$ is described now:

Connect $l_{jm}$ and $l_{kn}$ by an edge
Create $3$ new vertices $a$, $b$, $c$ (each gadget has its own three vertices like these)
Connect these $3$ vertices $a$, $b$, $c$ to form a $K_3$ cycle
Connect each of $a$, $b$, $c$ with both $l_{jm}$ and $l_{kn}$

Call the obtained undirected graph $G$. Set $k=2$. The reduction returns the instance $(G,k)$ of our problem.

Now, we prove the correctness of our reduction (for the undirected version).

If the given $\mathrm{NAE}$-$\mathrm{3SAT}$ is satiafiable, then given a solution, one can color all the $\mathrm{TRUE}$ literal-vertices $\mathrm{RED}$ and all the $\mathrm{FALSE}$ literal-vertices $\mathrm{GREEN}$. For each gadget described above, we color $a$ and $b$ by $\mathrm{RED}$ and $c$ by $\mathrm{GREEN}$. Next, we show that this is a solution to the produced instance of our problem.

Clearly, we use only $k=2$ colors as required. For each $K_3$ corresponding to one of the clauses, its $3$ vertices cannot be colored by the same color, because a solution to an $\mathrm{NAE}$-$\mathrm{3SAT}$ instance would make every clause containing both $\mathrm{TRUE}$ literal (colored $\mathrm{RED}$) and $\mathrm{FALSE}$ literal (colored $\mathrm{GREEN}$).

For each gadget of $2$ opposite literals $l_{jm}$ and $l_{kn}$, we have that these $2$ are colored by different colors. So, every cycle (contained in this gadget) that contains both these two vertices is already non-monochromatic. Only one other cycle (contained in this gadget) is the $K_3$ of $a$, $b$ and $c$. But as mentioned above, $a$ is colored $\mathrm{RED}$ and $c$ is colored $\mathrm{GREEN}$. All other possible cycles in $G$ need to cross from a $K_3$ clause to other $K_3$ clause by passing through a gadget. But, to pass through a gadget of, say $l_{jm}$ and $l_{kn}$ (colored by different colors), such a cycle has to be non-monochromatic.

Conversely, if we can color $G$'s vertices by $2$ colors without making any cycle monochromatic, then we will now show that the given $\mathrm{NAE}$-$\mathrm{3SAT}$ instance is satiafiable.

For each literal-vertex $l_{jm}=x_i$, if $l_{jm}$ is colored $\mathrm{RED}$, we assign $x_i$ to $\mathrm{TRUE}$, otherwise assign it to $\mathrm{FALSE}$.

For each literal-vertex $l_{jm}=\lnot x_i$, if $l_{jm}$ is colored $\mathrm{RED}$, we assign $x_i$ to $\mathrm{FALSE}$, otherwise assign it to $\mathrm{TRUE}$.

Since each clause is a $K_3$ cycle, it has to contain both $\mathrm{RED}$ literal-vertex (assigned to $\mathrm{TRUE}$) and $\mathrm{GREEN}$ literal-vertex (assigned to $\mathrm{FALSE}$).

It is left to prove the consistency of the above mentioned assignment. This is guaranteed by the gadgets. Suppose to the contrary that there exist two oppisite literals $l_{jm}$ and $l_{kn}$ colored by the same color, that w.l.o.g. we can assume to be $\mathrm{RED}$. Then it is impossible to properly color $a$, $b$ and $c$. Indeed, since $a$, $l_{jm}$ and $l_{kn}$ form a cycle, we deduce that $a$ must be colored $\mathrm{GREEN}$. Similarly, $b$ and $c$ are also colored $\mathrm{GREEN}$. But, now the cycle $(a,b,c)$ is monochromatic. Thus, the above assignment is consistent. And we obtain a solution to the given $\mathrm{NAE}$-$\mathrm{3SAT}$.

REDUCTION FOR DIRECTED VERSION

We use exactly the same above reduction. Now, we have to orient all the edges of $G$ to obtain a digraph. For each, $K_3$ clause cycle, we are free to choose one of two ways to turn it into a directed cycle (dicycle). For each gadget of two opposite literals $l_{jm}$ and $l_{kn}$, we can orient to have an arc $(l_{jm},l_{kn})$ (the other way can be finished similarly). Now, we orient to make $3$ cycles: $(l_{jm},l_{kn},a)$, $(l_{jm},l_{kn},b)$, $(l_{jm},l_{kn},c)$. Then, we make one more cycle, namely $(a,b,c)$. By orienting like this, we can use all the above arguments for the undirected version. Note that the possible dicycles that cross from clause to clause still have to be non-monochromatic.


Subset sum, pseudo-polynomial time dynamic programming solution? I found the P vs NP problem some time ago and I have recently worked on the subset sum problem. I have read Wikipedia article on the Subset Sum problem as well as the question Subset Sum Algorithm

I have looked at the problem and found  some solutions  but so far they seem to be NP,
I believe I can make a sufficiently fast algorithm in NP time.

My problem is I am not good in theory so it doesn't help me much to talk about the Cook-Levin Theorem or Non-Deterministic Turing Machines.

What I would like is an explanation of the pseudo-polynomial time dynamic programming subset sum that on Wikipedia.

I have read it and I believe I understand the general concept of why it is NP instead of P (related to the size of the input rather than the operations with it),
but I do not understand the algorithm.

I would appreciate if someone would put provide an example with some numbers and how it works. It would help me a lot because it would:

Give me ideas to improve my future algorithm
Help me understand intuitively when an algorithm is pseudo-polyonmial instead of NP.

Rephrasing Kaveh's comment as an answer:

If you bound the size the values in the input (bound the number of bits for each value to be logarithmic in the total number of bits of the input) then the problem can be solve in polynomial time using dynamic programming. If they are not bounded they can have values which are exponentially large and the size of the table for the dynamic programming would be exponential.


Do sparse graphs have to be large? I'm looking for a good definition of sparse graphs. Is a sparse graph effectively a big one, with millions/billions of nodes? An example from real world is the Facebook graph. Or can sparse graphs be in small networks as well?

The common definition is that a family of graphs $G = (V, E)$ is sparse if $m \in o(n^2)$, with $n = |V|$ and $m = |E|$. Formally, that requires the family to be infinite, and we only know something in the limit.

The definition does not apply to graphs of a fixed size per se. One would certainly want $m \ll n^2$ in some sense. For instance, if $m \leq 5n$ or $m \approx \log n$ you would probably say that your graph is "sparse".

You can bridge this gap by requiring a bit more on the asymptotic side. Say we call a family of graphs sparse if

$\qquad\displaystyle m \leq f(n) + O(1)$ with $f \in o(n^2)$;

then we may want to call every graph with $m \leq f(n)$ sparse. The implicit assumption is that the error term hidden in $O(1)$ is well-behaved.


Does exploiting a spatial Locality in Cache always leads to a lower miss rate? I've read that, incorporating many words(spatial locality) per cache blocks leads to lower miss rate. Is it the case always?
One possibility of such approach is to make a single cache block of size equal to the size of the cache, but that would be meaningless as far as benefits of memory hierarchy are concerned. Isn't it so?

Spatial (and temporal) locality are both heuristics. Many (in fact, most) algorithms run on data structures in some sequential manner, which many times means that the memory used is consecutive.

However, there are examples where spatial locality may actually be very bad. Perhaps the most common example is scanning a 2-dimensional array: consider an $n\times n$ array, then in the memory, it is represented as an $n^2$ length array, where the entry $i,j$ is in cell $i+n*j$.

If you scan the array row by row, then spatial locality is excellent, your cache will always prepare the next row.
However, if you scan by column, then not only will you always get a miss, but using spatial locality, you will actually retrieve the same rows over and over.


Are class methods closures? In the wiki article about closures one can read:

  closure ... is a function or reference to a function together with a
  referencing environment

At the same time in the wiki article about class methods:

  Accessor methods are used to read data values of an object. Mutator
  methods are used to modify the data of an object.

So, can I say that data is environment and class methods (accessors and mutators) are closures?

A closure is a piece of code together with an environments providing a
binding for its identifiers. In the case of a method, the identifiers
(at least some of them) are bound to data in specific instances of the
class, not just to the class itself.

The method provides only the code, of the function (in your first
quote), while the environment is provided by an instance of the class
(an object in your second quote). So it is the method together with
the object (class instance) that forms a closure.

Indeed, the class instance may be seen as the closure, since it
naturally carries the methods with itself formally, considering that
it is a closure for a tuple of functions, rather than a single one.
That is actually necessary, since the code of each function may refer
to the other function, meaning implicitly for the same environment.

Some of the first implementations of object orientation were actually
produced that way with higher order language. The creation of an
instance of a class was done by calling a creation function $Foo$ with
proper parameters. This function would return an instance represented
by a tuple of functions closed over the local environment of $Foo$, each
function being one of the methods for the class. Actuallly these method
function were declared inside $Foo$ so as to see all the local
identifiers in $Foo$, which are the data for this instance being created, and otherwise invisible outside $Foo$.

Each new call of $Foo$ would create a new call instance, i.e. a new
environments on which execute the methods.

But the syntactic sugar may vary significantly.

Historically, afaik, the name closure was used for a function value $g$
returned by a call to a function $F$, though it is created (declared,
to say it approximately) inside $F$ and can thus see and use any
entity $x$ declared in $F$. Normally, what is declared in $F$ ceases
to exist, to be accessible, as soon as $F$ is exited.  But when $F$
returns such a function valued result $g$, the system has to preserve
any identifier $g$ may be using since $g$, as a function value,
survives the termination of the call to $F$. All identifiers used by
$g$ are preserved in an environment and $g$ together with this
environment is called a closure.

Note that $g$ is a function value, not anything being called. The
environment of this closure is preserved as long as the function is
callable. Several function can be closed at the same time on the same environment.


boolean expression syntax checking i am trying to formulate an algorithm for syntax checking for simple boolean expression like (var1 = 10) or (var2 > 100).
evaluation part seems to be easy as i will convert infix to postfix and evaluate postfix without 'paren()'.

i am not fully sure which method should i be using.

can any one point me to a book with algorithm or a link.

What you are describing is part of the area of knowledge known as compiler theory, specifically parsing. One of the classical books is the dragon book. Parsing and evaluating expressions like yours is usually done in three interlocked steps:

Lexical analysis. This part is in charge of converting the input into a sequence of "lexemes". It will convert your example into the lexemes "(" VARIABLE "=" NUMBER ")" "or" "(" VARIABLE ">" NUMBER ")". This step is implemented using regular automata.
Syntax analysis. This part construct a parse tree of your expression. In your case, the parse tree (generated using Miles Shang's online tool) will be:

This step is implemented using context-free languages, either using a table-based approach or using recursive descent.
Semantic analysis. In your case, this part will evaluate the expression recursively using the parse tree, making use of attributes stored at the meta-lexemes VARIABLE and NUMBER.


Why is the complexity of the BFS O(V + E)? Consider the algorithm (from another question):

set start vertex to visited
load it into queue
    while queue not empty
        for each edge incident to vertex
             if its not visited
                 load into queue
                 mark vertex

The complexity of the algorithm is defined as the upper bound of times the inner loop can run, right? Well, considering a complete graph. For each one of its N vertexes, we run the check if its not visited N-1 times. So, that's N * (N-1) tests, which is quadratic. What is wrong with this view?

Overall, BFS accesses (and processes) each edge constant times (twice actually; we assume an undirected graph), costing $O(E)$ total time in edge processing. Similarly, all the vertices are totally accessed (including queue operations and checking operations) $O(E) \cdot O(1)$ times. The overhead for initialization is $O(V)$. Thus the total running time of BFS is $O(V + E)$.

This can be viewed as a simple instance of aggregate analysis.


Duplicate elements in Queue for BFS Maze Algorithm I'm fairly new to studying data structures and algorithms.

I've implemented a non-recursive BFS on a 2d "maze array" which seems to work well. It finds the position of 2 in an array of 1s (walls) and 0s (spaces), marking visited positions with 3.

However, I notice that there are duplicate values in the Queue. I understand that I should avoid visiting already visited positions. However the queue contains only "prospective" positions which are yet to be visited. Should I modify the algorithm to not enqueue positions which it already contains? Will the algorithm still work if I do so?

As far as I know I have implemented the following algorithm:

Create a queue for positions yet to explore, and enqueue the entrance (0,0)
While the list is not empty
     dequeue
     If it is the goal position,
            exit displaying position and success message
     Otherwise,
            mark the position as visited, and enqueue all valid neighbors (not walls and not visited)
If the list is empty and the method has not returned, there is no path

Some sample output is below:

Enqueueing (0,0)
Queue contents: [(0, 0)]
Press Enter to continue:
Dequeueing
Current position: (0, 0)
Marking (0, 0)
[3, 1, 1, 0]
[0, 0, 0, 1]
[0, 0, 1, 0]
[1, 0, 0, 2]
Enqueueing coordinates of valid positions in 4 directions.
Queue contents: [(0, 1)]
Press Enter to continue:
Dequeueing
Current position: (0, 1)
Marking (0, 1)
[3, 1, 1, 0]
[3, 0, 0, 1]
[0, 0, 1, 0]
[1, 0, 0, 2]
Enqueueing coordinates of valid positions in 4 directions.
Queue contents: [(1, 1), (0, 2)]
Press Enter to continue:
Dequeueing
Current position: (1, 1)
Marking (1, 1)
[3, 1, 1, 0]
[3, 3, 0, 1]
[0, 0, 1, 0]
[1, 0, 0, 2]
Enqueueing coordinates of valid positions in 4 directions.
Queue contents: [(0, 2), (2, 1), (1, 2)]
Press Enter to continue:
Dequeueing
Current position: (0, 2)
Marking (0, 2)
[3, 1, 1, 0]
[3, 3, 0, 1]
[3, 0, 1, 0]
[1, 0, 0, 2]
Enqueueing coordinates of valid positions in 4 directions.
Queue contents: [(2, 1), (1, 2), (1, 2)]
Press Enter to continue:
Dequeueing
Current position: (2, 1)
Marking (2, 1)
[3, 1, 1, 0]
[3, 3, 3, 1]
[3, 0, 1, 0]
[1, 0, 0, 2]
Enqueueing coordinates of valid positions in 4 directions.
Queue contents: [(1, 2), (1, 2)]
Press Enter to continue:
Dequeueing
Current position: (1, 2)
Marking (1, 2)
[3, 1, 1, 0]
[3, 3, 3, 1]
[3, 3, 1, 0]
[1, 0, 0, 2]
Enqueueing coordinates of valid positions in 4 directions.
Queue contents: [(1, 2), (1, 3)]
Press Enter to continue:
Dequeueing
Current position: (1, 2)
[3, 1, 1, 0]
[3, 3, 3, 1]
[3, 3, 1, 0]
[1, 0, 0, 2]
Enqueueing coordinates of valid positions in 4 directions.
Queue contents: [(1, 3), (1, 3)]
Press Enter to continue:
Dequeueing
Current position: (1, 3)
Marking (1, 3)
[3, 1, 1, 0]
[3, 3, 3, 1]
[3, 3, 1, 0]
[1, 3, 0, 2]
Enqueueing coordinates of valid positions in 4 directions.
Queue contents: [(1, 3), (2, 3)]
Press Enter to continue:
Dequeueing
Current position: (1, 3)
[3, 1, 1, 0]
[3, 3, 3, 1]
[3, 3, 1, 0]
[1, 3, 0, 2]
Enqueueing coordinates of valid positions in 4 directions.
Queue contents: [(2, 3), (2, 3)]
Press Enter to continue:
Dequeueing
Current position: (2, 3)
Marking (2, 3)
[3, 1, 1, 0]
[3, 3, 3, 1]
[3, 3, 1, 0]
[1, 3, 3, 2]
Enqueueing coordinates of valid positions in 4 directions.
Queue contents: [(2, 3), (3, 3)]
Press Enter to continue:
Dequeueing
Current position: (2, 3)
[3, 1, 1, 0]
[3, 3, 3, 1]
[3, 3, 1, 0]
[1, 3, 3, 2]
Enqueueing coordinates of valid positions in 4 directions.
Queue contents: [(3, 3), (3, 3)]
Press Enter to continue:
Dequeueing
Current position: (3, 3)
Goal reached at (3, 3)

Yes.  There is no point having duplicates in the queue, so don't enqueue a position if (a) it has already been visited, or (b) it is already on the queue.

What happens if you skip checking whether it is already on the queue?  Depending on how the rest of your code works, this could slow down your implementation significantly (it could increase the asymptotic running time from linear to quadratic).


Two's complement overflow I know that in the case of a 16 bit word, if we have x - 115 in decimal, the smallest x that would cause overflow would be (32767 + 115 + 1)= 32883 because it would represent a number that is larger than the largest positive integer we could represent in a 16 bit word.
However, I was wondering what would the largest value of x be? would it be (2^16)? which would cause 2 carries after the addition.  Or would the largest x be a number that would only result in 1 carry alone?

You get overflow if the result is larger than the maximal integer, in this case 32767. You get underflow if it is smaller than the minimal one, in this case -32768. (In the context of floating-point operations, underflow happens when a non-zero number is rounded to zero.)


Understanding state table for turing machine I'm having trouble understanding state tables for turing machines where the state table shown in the above image is supposed to show the change from the top turing machine to the bottom such that an extra 1 was added at index 5. I don't see how when S0 reads 1 (at start, index 1) and shifts the head right it then reads 0 and then writes 1, as when it shifts right shouldn't the head be at index 2 and read 1? And if the head was at index 2 then the finish at S2 would be at index 2 as well (since it shifts left and then right again)?

They're the same Turing Machine, to be specific - the top diagram is a representation of the tape before the TM has run, and the bottom diagram is after.

There's no key regarding how to read the state transitions but I'm assuming >> means shift right one cell, << means shift left one cell and 1 means stay put.

You are right that the first move would be to index 2, using the first rule. But this rule applies three more times still, so the head ends up at index 5, where it encounters 0 and enters state S1 via the second rule - at the same time writing 1 at index 5.

The head then shifts back all the way to index 0 (one cell at a time) using the third rule, at which point the fourth rule is used (read 0, switch to S2, shift right). So it moves right to index 1 and then stops, as S2 is the final state.


Reducing a graph without changing its chromatic number Does reducing a graph (removing or replacing vertices or edges) without changing its chromatic number has a specific name?

Take this cactus graph as an example (although my question is about an arbitrary graph):

The edges with vertex of degree 1 could be removed without affecting the vertex chromatic number. I think something similar should be possible with cycles e.g. removing the two vertices in the bottom of the cactus should not affect its chromatic number.

Are there polynomial algorithms that removes edges to the extent that no more edge can be removed without affecting an arbitrary graph chromatic number? I would prefer not to reinvent the wheel.

If the answer is no, are there algorithms that remove an arbitrary number of edges without affecting an arbitrary graph chromatic number?

My goal is to simplify graphs before feeding them into other algorithms.

I will also appreciate references to relevant literature. Thank you!

The general idea of taking a problem instance and reducing it to a smaller one that gives the same answer is called kernelization. It's widely used in parameterized complexity theory and not just for colourings.


Check if knapsack problem instance is unsolvable Is it possible to easily check if an instance of the 0-1 knapsack problem is unsolvable? Example: Assign 10 40-min tasks to 8 employees that have 60 minutes available each. Clearly, this instance is unsolvable as a 0-1 knapsack problem (but solvable as a fractional knapsack problem). I don't want to solve the 01-knapsack problem, but just detect if it is NOT solvable. Thanks in advance!

EDITED PROBLEM 1 - THOROUGH PROBLEM DESCRIPTION

Below is a more thorough problem description.

Tasks

I have a set of tasks with a given duration and a given time window each task has to be performed within (e.g the task duration for a given task could be 20 minutes and it has to be performed in the time interval 08:00-09:00). In addition, each task has a required skill, meaning that the employee carrying out the task needs to have a certain competence level (e.g tasks with required skill equal to 2 can only be carried out by employees with a competence level greater than or equal to 2).

Employees

I have a set of employees that work shifts. E.g an employee work from 08:00 to 13:00. Each employee has a given competence level, described above. The tasks are supposed to be allocated to the employees, and an employee cannot perform more than one task at the same time. E.g the same employee cannot perform BOTH task 1 (duration 10 minutes and time window 08:10-08:20) and task 2 (duration 30 minutes and time window 08:10-08:45). In addition, there are some tasks that a given employee cannot perform due to other reasons.

Problem

I want to check (preferably in polynomial time) a given problem instance (with tasks and employees) is not solvable, meaning that there exists some conflict such that it is impossible to allocate all tasks (see example above in original question formulation). To my understanding, it is NP-hard to solve the problem, but I just want to prove/detect that a given instance is unsolvable. Is it possible to easily check if there does not exist a possible assignment of tasks to employees?

EDIT 2 - BETTER DEFINITION OF THE GOAL

To be clear, I don't want an algorithm that ALLWAYS finds out if an instance is unsolvable or not. I am just looking for a way (an algorithm) that as OFTEN AS POSSIBLE finds out if the instance is unsolvable, and if the algorithm is uncertain (some efficient test did not detect that the instance was unsolvable) then I am fine with the problem instance being either solvable or unsolvable. So the algorithm I am looking for should detect as many "unsolvable instances" as possible, but not all.

Thanks in advance for your answers and contributions!

This is a complex set of constraints.  The standard way to solve this kind of problem is using integer linear programming (ILP).  Solving ILP instances is NP-hard -- so there is unlikely to be any polynomial-time algorithm -- but in practice, on real-world scheduling problems, solvers can often find a solution in a reasonable amount of time.  For your parameters (10 employees, 75 tasks, a few dozen time slots), I would expect that ILP might be very effective.  This kind of approach is widely used in operations research for scheduling.

So, use an ILP solver.  You can even set a time limit, and then it will return either "solution found", "no solution exists", or "time exceeded".  That will meet your requirement of identifying some instances that are unsolvable, efficiently.


Relation between "undecidability of arithmetic" and "godel's incompleteness theorem"? There is a theorem that states that arithmetic is undecidable: i.e. $Th(\mathcal N)$, the set of all sentences in the standard arithmetic structure $\mathcal N=(\mathbb N,+,\cdot , 0,1)$ where the symbols are interpreted in the standard way, is undecidable.

Godel's first incompleteness theorem states that there does not exist a set of axioms from which we can prove all true arithmetic statements: There does not exist a set of first order formula's $\Phi$ that is consistent and decidable, such that for any first order $(+,\cdot,0,1)$ sentence $\phi$, we have $\Phi\vdash\phi$ or $\Phi \vdash \neg \phi$. By the completeness theorem we could have instead written "$\Phi\models\phi$ or $\Phi \models\neg \phi$"

But since we can construct a first order proof system that is complete, in the sense that all valid sentences can be proven, doesn't this boil down to the same thing?

Isn't godel's incompleteness theorem simply an implication of the undecidability of arithmetic?

Yes, if we know that $Th(\mathcal{N})$ is undecidable then we know that it is not computably axiomatizable, and in particular we know that no computably axiomatizable theory consisting only of true sentences of arithmetic is complete.

Here I'm adopting a Platonist view with regards to $\mathcal{N}$: I assume that "the" set of natural numbers exists, and "true" means "true in that structure.

However, there are a couple points here:

How do we know that $Th(\mathcal{N})$ is undecidable?
What about strengthenings of Godel's theorem, like "No consistent computably axiomatizable theory of arithmetic extending PA (or even Q) is complete"? (This is an extension due to Rosser of the theorem as originally proved by Godel, but is basically just one clever idea on top of the usual proof.)

Ultimately, (1) really already uses the key idea/argument of Godel's theorem, while (2) points out the limitations of measuring the complexity of a single structure.

So this shouldn't be construed as trivializing Godel's theorem in any way; in particular, I object to the word "simply" in the last line.


Enumerating pairs of disconnected cliques in a graph Given an unweighted graph $G = (V,E)$. I am interested in enumerating all pairs of disconnected cliques, i.e. there should not exist any edge between two cliques. (For example, there would not exist any such pair in a complete graph). A clique could be of any size $\geq 1$.

Are there any standard approaches to solve this problem? If so, could someone please highlight the sources or suggest some approaches?

I figured out this solution while discussing with a Professor.

The above problem could be formulated into a clique search problem. Let the input graph be $G_1 = (V_1,E_1)$. Create a duplicate $G_2 = (V_2,E_2)$ of $G_1$. Let vertices in $V_1$ be denoted by $\{v_{11},v_{12},...,v_{1k}\}$ and their duplicates in $V_2$ be represented by $\{v_{21},v_{22},...,v_{2k}\}$. Now, for each pair of vertices $(v_{1i},v_{1j})$ in $G_1$ without an edge with $(i<j)$, connect $(v_{1i},v_{2j})$. Then, all the desired pairs of disconnected cliques of $G_1$ can be obtained as cliques of $G_1 \cup G_2$ that have vertices in both $G_1$ and $G_2$.


Transformation from one feature space to another I have found the following example:

  As an example consider the case when the input space  $ {\mathcal{X}}$
  consists of images of  $ 16\times 16$ pixels, i.e. $ 256$ dimensional
  vectors, and we choose $ 5$th order monomials as non-linear features.
  The dimensionality of such space would be

  $\displaystyle \left(\begin{array}{c}5+256-1\\ 5\end{array}\right) \approx 10^{10} \;$

  Such a mapping would clearly be intractable to carry out explicitly.
  We are not only facing the technical problem of storing the data and
  doing the computations, but we are also introducing problems due to
  the fact that we are now working in an extremely sparse sampled space.
  By the use of the SRM principle, we can be less sensitive to the
  dimensionality of the space and achieve good generalization.

  The problems concerning the storage and the manipulation of the high
  dimensional data can be avoided. It turns out that for a certain class
  of mappings we are well able to compute scalar products in this new
  space even if it is extremely high dimensional. Simplifying the above
  example of computing all $ 5$th order products of $ 256$ pixels to
  that of computing all $ 2$nd order products of two ''pixels'', i.e.

  $\displaystyle {\boldsymbol{x}} = (x_1,x_2)$   and$\displaystyle \quad\Phi({\boldsymbol{x}}) = \left(x_1^2,\sqrt{2}x_1x_2,x_2^2\right)\;$

The problem that I have is in understanding the last formula, from where does the author gets those values for the individual transformation? To me, it seems that he is applying the formula of analytical geometry of a circle, but I am not quite sure.

Also how does the author apply the transformation from $ {\mathcal{X}}$ to $\displaystyle\quad\Phi({\boldsymbol{x}})$?

This is just the explicit form of the feature map for a homogenous, degree 2 polynomial kernel.  Here your input space is $\mathbb{R}^2$ and the feature space can be identified with $\mathbb{R}^3$.  The point the author is making is that instead of computing the feature map explicitly, and then taking the Euclidean inner product $\langle \Phi(p),\Phi(q)\rangle$, you can just compute $\langle p,q\rangle^2$.


What is the relationship between Turing Machines with a finite tape and Finite State Automata? I seem to recall from an undergraduate class that for a Turing Machine with a finite tape there will always exist a corresponding Finite State Automata, but I've been unable to find this confirmed anywhere on the internet. Is this actually the case or am I misremembering?

It depends what you mean by "finite tape". If you bound the length of the tape by some function of the input, then no - you can recognize non-regular languages. For example, consider LBAs.

But if you mean a bounded tape, where the tape has $k$ cells for some fixed $k$, then yes - you indeed get a model which is equivalent to DFAs.

To prove this, consider what information you need to determined the future of a run of a TM: you need the contents of the tape, the location of the head, and the state. If the tape has a constant number of cells, and the alphabet is fixed, then you have a constant number of configurations, which you can encode as states of a finite automaton.


Say that a stack frame only contains total functions: could the maximum stack size be statically determined? Say that you have a program with only total functions, or if that is impossible, consider a subset of the program with only total functions. Is it theoretically possible to statically determine the maximum size of the stack frame at runtime? The language may have other characteristics that are relevant/necessary (such as a specific type system).

No. That would allow you to determine the runtime of any given (recursive) program (assuming it always terminates), but that is not a computable problem.


Combinations (repetition not allowed & order not important) How to compute a table of numbers (all possibilities), where repetition is not allowed and order is not important.
Example:
I have a set of prime numbers. In this example I have four: {3,5,7,11}, but it can be anything, and I want to choose every pair out of that set.
To make things easier, I want to compute the indices to get those pairs of prime numbers. The set of indices is then {0,1,2,3}. We pick 2 out of 4 elements. So how do we compute the permutations or combinations:
0,1   (3,5)
0,2   (3,7)
0,3   (3,11)
1,2   (5,7)
1,3   (5,11)
2,3   (7,11)

?
It was difficult to find examples on the web, because they either allowed repetitions or were order was important. Pls answer with pseudocode or c/c++ if you can.

You seem interested in just pairs of indices. Then, if you have $n$ elements you can just generate all pairs of indices  $(i,j)$ with $0 \le i < j < n$.
For i=0,1,...,n-2:
   For j=i+1, i+2, ..., n-1:
      Output (i,j)


Is memorization necessary in learning computer science? Backgrounds
Hi guys, I am now trying to teach myself some basic computer science theories. Specifically, I am using the book, CSAPP (computer systems, from a programmer’s perspective) and 15-213 taught by CMU
Question
My question is whether I need to memorize all the details covered in such theoretical courses (eg. the structure of an ELF file, the process of linking). If not, what is the methodology in approaching computer science theories.
This becomes even confusing when we have got searching engines now, considering we can always search for the facts that we need. If so, what is the purpose of learning? What shall we learn?

It's hard to answer what you "need", as that depends on your purpose, and hard to answer this question concretely, as it is very broad.  I recommend you focus on learning concepts and ideas, as these are more likely to be of lasting use.  Sometimes, though, to understand how some interesting capability is achieved, you will need to understand the details of how it is implemented.  In general, if you pick a good textbook, then it's likely that there will be a lot of worthwhile material in there.  Saying much more might require getting into specifics.


Is word size, the size of a memory location? the size of the data bus? or the cpu register size? Is word size, the size of a memory location? the size of the data bus? or the cpu register size?

Suppose you have a computer,

memory address #0 has byte AB  memory address #1 has byte F3  memory address #2 has byte EA  So each memory address stores one byte.

And you have a data bus that can pick up 4 contiguous memory locations, bytes, at a time. So I suppose if the CPU wanted address 0, then it'd pick up address #0,#1,#2,#3    And if the CPU wanted address 1, then it'd pick up #1,#2#,3#,#4

And Case A, say the CPU register size is 64bit.   (would that require two fetches? i'm not sure if that'd work).   So alternatively, Case B,  Let's say the CPU register size is 32bit

What is the word size?  Is it the data bus size, the memory location size, or the cpu register size?

This is one of those terms that can mean different things depending upon who you ask and the context in which it is asked.

Usually a processor's word size is defined as the largest size integer which it can operate on with a single arithmetic instruction.  For example, 64 bit computer can add or subtract 64 bits with a single instruction.  But that same computer may be able to operate on bytes, 16 bit words, and 32 bit longwords.

Don't equate the memory path with the computer's word size.  Often data is moved into and out of cache in a fixed size block that is a multiple of the computer's word size.  A 64 bit CPU has 8, 8 bit bytes per word but might use a 64 byte cache line and move data into and out of memory in cache block chunks, even if the CPU is only accessing 1 byte of the cache block.  OR conversely, the data path to memory could be smaller, as the case with the old 8088 CPU.   It used 16 bit CPU registers and did 16 bit arithmetic, but had an 8 bit data bus.  It had to do 2 memory transfers to load or store a register.

And then there are fixed definitions for a word size, for example...

DEC had a problem with just saying WORD especially on VAX architecture, mostly because the company had built so many different computers with different natural word sizes (9, 18, 36, 12, 16, 32 and 64 that I can think of) and the VAX was capable of working with a large variety of data sizes.  So they decided to define terms like WORD to have more definite meanings.
Byte = 8 bits,
Word = 16 bits,
Longword = 32 bits,
Quadword = 64 bits,
Octaword = 128 bits

This took much of the confusion out of discussions when a processor was capable of handling multiple different data sizes.

edit - I didn't really address this part of the question:
"And you have a data bus that can pick up 4 contiguous memory locations, bytes, at a time. So I suppose if the CPU wanted address 0, then it'd pick up address #0,#1,#2,#3 And if the CPU wanted address 1, then it'd pick up #1,#2#,3#,#4"

Not usually.
IF a 64 bit computer is capable of addressing Longwords on a byte boundary, normally the system would load the cache block containing the address 0 from memory into cache.  Often that will be on a multiple word cache size.   So in the example I gave with a 64 byte cache line, the hardware would move the first 64 bytes into cache as a chunk.  The CPU would then access the bytes from cache as you describe (well sort of, it may have to shift bytes to get them loaded correctly).  If the longword you attempted to load spanned 2 cache blocks, the hardware would have to load 2 cache blocks (128 bytes) to access the 4 you were interested in. Or in the example you gave with a 32 bit data bus, it would have to load 64 bits (2 lines) to get the 32 that you want.   If possible, it's best to align data on its natural boundary to avoid this and other data manipulations required to deal with unaligned data.


Why is Byzantine Generals Problem with traitors possible? My question is what makes the Byzantine Generals Problem possible to solve in some cases where traitors exist, for example in the case where there are 4 generals with 1 traitor?

If the generals must either all attack or all retreat at the same time, then surely the traitorous general can simply say "yeah sure we'll attack" and then retreat as the other 3 generals plunge into their deaths.

I suspect the answer has something to do with different variations of the problem, but I was unable to find any other definition for the Byzantine Generals Problem other than "all must either attack or retreat". Almost all of the search results are blockchain related advertisement, and the Wikipedia article doesn't provide a different definition for the goal of the generals.

Quoting from the abstract of the original paper introducing the Byzantine Generals problem (with my emphasis):

  The problem is to find an algorithm to ensure that the loyal
  generals will reach agreement.

If you read further in the paper, they reduce the problem to agreeing on a single bit: "Attack" or "Retreat". The question is can the loyal generals reach consensus amongst themselves when they don't know who the traitors are.

So for your proposed scenario, as far as the Byzantine Generals problem is concerned, the only question is whether all the loyal generals can agree on the plan, not whether the plan is workable. At any rate, "all attack" either means "all [loyal generals] attack" which is essentially what would be produced by a Byzantine fault-tolerance algorithm, or it means "all [generals, loyal and traitorous alike,] attack" which would simply be silly. In this thought experiment the generals know that there are potentially traitors so they would presumably not propose a plan that only works if there are no traitors. What is actually being agreed upon, e.g. the "goal", is outside the scope of the Byzantine fault-tolerance algorithm, of course. The algorithm doesn't care whether the question is "should we attack or retreat?" or "should we choose pink or chartreuse for the new standard?"


On Tarjan's paper "Finding a Maximum Clique" In his paper, "Finding a Maximum Clique" from 1972 Robert Tarjan introduced an algorithm that finds maximum cliques in $O(1.286^n)$. You can find a link to his paper here.
In the second page of the introduction he states the following lemma.
Let $G = (V,E)$ be a graph and $S \subseteq V.$ Then
$$
||G|| = \max_{\text{clique } C \text{ in } G_S} \{|C| + ||G_{A(C)\setminus S}||\}
$$
where $||G||$ is the size of the maximum clique in $G$ and $A(C)$ is the set of adjacent vertices to one or more elements in $C$.
This does not make sense to me, for example if we let $S$ be the set containing just one isolated vertex, then $\max_{\text{clique } C \text{ in } G_S} \{|C| + ||G_{A(C)\setminus S}||\} = 1$, since $A(C) \setminus S = \emptyset \setminus S = \emptyset$.
Even worse, we can take $S = \emptyset$ and then the lemma falls apart.
What am I missing?

You definition of $A(C)$ is wrong. It is the set of vertices adjacent to all vertices in $C$:
$$
A(C) = \{ v \in V : \forall u \in C, (u,v) \in E \}.
$$
In particular, if $C = \emptyset$ then $A(C) = V$.
In your example, suppose that $S = \{v\}$. Let's see what $|C| + \|G_{A(C) \setminus S}\|$ amounts two for all choices of $C$:

If $C = \emptyset$, then $A(C) \setminus S = V \setminus \{v\}$, and so $|C| + \|G_{A(C)\setminus S}\|$ is the maximum size of a clique in $G$ that doesn't contain $v$.
If $C = \{v\}$, then $A(C) \setminus S = N(v)$, the set of neighbors of $v$. Therefore $|C| + \|G_{A(C) \setminus S}\|$ is the maximum size of a clique in $G$ that contains $v$.

So in this case, the formula is correct.
When $S = \emptyset$, the formula just states that $\|G\| = \|G\|$.


Constructing a crown graph given an independent set A crown in a graph $G$ is a pair $(H, C)$, where $H \subseteq V(G)$ and $C \subseteq V(G)$ with $H ∩ C = ∅$ such that the following conditions hold:
(a) The set of neighbors of vertices in $C$ is precisely $H$, i.e. $H = N(C)$,
(b) $C = C_m \cup C_u$ is an independent set, and
(c) There is a perfect matching between $C_m$ and $H$
Theorem:
Any graph $G(V,E)$ with an independent set $I$, where $|I| ≥ \dfrac{2n}{3}$ , has a crown $(H, C)$, where $H ⊆ N(I), C ⊆ I$ and $C_u \ne ∅$, that can be found in time $O(nm)$ given $I$. $(n=|V|, m = |E|)$

I am trying to code an algorithm to find such a crown in $O(nm)$ time
The only way I could think of finding a crown given an independent set is to take subsets of the set: $I$ and check for all the three conditions of a crown. However, taking all subsets of $I$ will take exponential time right? How to find it in $O(nm)$ time. I just want an algorithm with polynomial time. It need not be $O(nm)$... It can be in the form $O(n^c m^d)$ where $c,d$ are constants.

In the book Kernelization by Fomin, Lokshtanov, Saurabh, Zehavi (which is downloadable as a PDF on the first author's homepage) you find Chapter 4. Crown decomposition.  This should point you to the answer.


Studying Skiena. War Story: What’s Past is Prolog I am reading The Algorithm Design Manual, 2nd Edition.
The book gives an example task and then explains how to solve it step by step.
(The task and solution is detailed here)

But I don't follow one step from the solution. That step doesn't contain enough details for me so I don't understand it. I'm asking if someone can explain it.

Below I rewrote the task in a shorter form than in the book:

Given n ordered strings (lets call them rules) of m characters. The strings are indexed starting from 1 (not 0)

The goal is to construct the trie with the minimum possible number of edges. The leaves of the resulting trie (each leaf represents a string) have to be in the same exact order as the given collection of strings.

We are free to pick an arbitrary character position on each step of constructing the trie (e. g., we are free to start constructing the trie from character position 2 as opposed to starting from 1). Thanks to this ability we can minimize the built trie. Lets call picking a character - probing.

Example:

From the four rules below it's possible to build different tries depending on the order of picking characters from the strings.

S1: (a,a,a)
S2: (b,a,a)
S3: (c,b,b)
S4: (d,b,b)

The book says that

  Probing at the p-th position, 1 <= p <= m, partitioned the rules into runs R1,...,Rr, where each rule in a given run Rx = Si,...,Sj had the same character value of Si[p].

  Since the rules were ordered, each node in the subtree must represent the root of a run of consecutive rules, so there were only ${{n}\choose{2}}$ possible nodes to choose from for this tree...

  ...

  The rules in each run must be consecutive, so there are only ${{n}\choose{2}}$ possible runs to worry about.

My question: How does the fact the rules are consecutive lead to the inference that there are ${{n}\choose{2}}$ possible nodes/runs after probing at the p-th position?

Each (non-trivial) run is given by two (different) indices, marking the beginning and end of the run, so if the sequence is of length $n$, there are $\binom{n}{2}$ possible runs. If we only consider maximal runs, there are at most $n$ (or even less, if we don't consider trivial runs).


Copying items in arrays while checking their indexes Array $P$ of length $n$ is a permutations of $\{0, ..., n-1\}$

  Write a code, which would in $O(n)$ create an array $R$ of length $n$, so
  for values $x_i, x_j \in P$,  $R[x_i] < R[x_j]$ if $x_i$ is on the left of $x_j$ ($i<j$).

This is a algorithmization problem that's recurring in the final's test each year and I'm stuck with it for weeks. I know that I'm supposed to show my work before asking here, but I didn't know how to start.

Could you at least point me to the right direction? What technique do I use, dynamic programming? Is this a problem for a specific algorithm?

All you're looking for is some mapping between the elements of $P$ and their indexes, that can be found in $O(1)$ for each element of $P$. Suppose given $p_i \in P$, you can use the fact that $p_i \in \{0, \dots n-1\}$, and that no $p_j \in P$ exists s.t $p_j = p_i$ (other than $j=i$).

How will you do it? Set $R[x]$ to the index of element $x \in P$.

Since $x$ is unique, no elements of $R$ will be overridden.
Suppose $p_i , p_j \in P$, and $p_i$ occures before $p_j$ ($i<j$). Then $R[p_i] = i$ and $R[p_j] = j$, and it holds that $R[p_i]<R[p_j]$

You should be able to take it from here.


Probability of data loss for mirrored,3 disk system I am reading the book Database Systems the Complete Book 2nd Edition.
A slightly modified Question 13.4.5 states:

  Suppose we use three disks as a mirrored group; i.e., all three hold
  identical data. If the yearly probability of failure for one disk is
  F, and it takes H hours to restore a disk, what is the yearly probability
  data loss?

My answer is $(F*(F*H/365*24)^2)*6$

I would like to know if I am right. I will explain the reasoning behind my answer:

In order for data loss to occur, all 3 disks must fail within a time period of H hours.

The probability that the first disk fails is $F$. The probability that the second and third disks fail within $H$ hours of the first disk failing is $(F*H/365*24)^2$.

Thus the probability of all disks failing within a time period of H hours is $F*((F*H/365*24)^2)*6$.

The reason we multiply by 6 is because there are 6 ways in which this event could happen:

123
132
213
231
312
321

I have trouble with probability when dealing with events that can occur in multiple ways. So the only part of the reasoning that I am unsure about is the part where I multiply by 6. Are all 3 disks failing one event, or are they 6 different events?

Let us look at the probability of the "123" event happening. That is, Disk 1 fails, and then Disk 2, and then Disk 3, and all of these happen within a span on $H$ hours. Your claim is that the probability of this is $F ∗ (\frac{FH}{365∗24})^2$. But the $\frac{FH}{365∗24}$ term only denotes the probability of a disk failing in the $H$ hours after the first  disk fails. In particular, it does not consider the ordering constraint of "Disk 2 fails before Disk 3 fails".

Instead, what $F ∗ (\frac{FH}{365∗24})^2$ denotes is the probability that Disk 1 fails, and in the ensuing $H$ hours, both Disk 2 and Disk 3 fail. So this captures both the events "123" and "132".

Similarly, the probability of either the event "213" or "231" happening would be $F ∗ (\frac{FH}{365∗24})^2$. And similarly for the events "312" and "321" combined.

So the final answer should be $(F ∗ (\frac{FH}{365∗24})^2) * 3$, and not $(F ∗ (\frac{FH}{365∗24})^2) * 6$.


Proofs of $P^{\#P}\subseteq P^{PP}$ and $\#P\subseteq FP^{PP}$ $P^{\#P}\subseteq P^{PP}$ and $\#P\subseteq FP^{PP}$ are known and usually handwaived as exercises. I could not find proofs of these two results.

What is a rigorous proof for $P^{\#P}\subseteq P^{PP}$ and $\#P\subseteq FP^{PP}$?

How is having an oracle to $\#P$ at most as powerful as having an oracle to $PP$?

This is not the full proof but the complete idea:
Let Turing machine $M$, define  $L_M$  be the language defined as  $L_M = \{ ((x, y) \in \Sigma^*\times \mathbb{N}  ~|~ \#\text{accepting path of } {M}(x) > y \} $
Then prove that $L_M\in PP$.
Now use the binary search technique to compute the function g(x) in $\#P$ using $L_M$.
And other way around its easy by using $\#P$ function TM you can always answer whether no. of accepting paths are more $\frac{1}{2}$ or not.
Let $L\in P^{\#p}$, then there is a deterministic oracle Turing machine $M'$ that runs polynomial time, and a function $g\in \#p$
such that  $L= M'^{g}$. Let $M$ be a poly time Turing machine that uses at most $poly(n)$ non-deterministic steps such that $g(x)=\# acceptig pathof M"(x)$.   Use the standard binary search technique to show that  $g(x)$ can be computed  using $O(n)$ many queries to the language $L_M$.
$x$, oracle access to $L_M$ and output $g(x)$.

Initialize $p=|x|$, $y=2^p$.

Repeat steps 3 & 4 until $p\ge 0$

Query $(x,y)$ to the oracle;  If YES, then set $y=y+2^{p+1}$;
Else
break .

Set $p=p-1$

Now we know the range for g which is $2^{p-1}<g<2^{p}$
$use binary search technique in this range and since there can be exponential terms hence binary search technique will take O(|x|) time.
Clearly, the algorithm  above runs in time ${\sf poly}(n)$, and hence computing $g$ can be done in $poly$ with oracle access to $L_M\in PP$.


Which AC-3 algorithm is being used here? This is the illustration of the AC-3 algorithm for four queens from exhaustive study of essential constraint satisfaction problem techniques based on N-Queens problem by Md. Ahsan Ayub, Kazi A Kalpoma, Humaira Tasnim Proma, Syed Mehrab Kabir and Rakib Ibna Hamid.

I am confused whether this is pure AC-3 or AC-3 with backtracking. Which one is it?

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

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

Here is a relevant excerpt from the article.

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


What algorithm solves high-order unification for untyped terms in most cases? High-order pattern matching is an undecidable problem. That means there is no algorithm that, given an equation a => b, where a and b are terms on the simply typed lambda calculus, a containing free variables, finds a substitution S such that aS => b, where => stands for "has the same beta normal form" (up to variable renaming). For example, given the following problem:

a = (λt . t
    (F (λ f x . (f (f (f x)))))
    (F (λ f x . (f (f x)))))
b = (λ t . t
    (λ f x . (f (f (f (f (f (f x)))))))
    (λ f x . (f (f (f (f x))))))

One can come with the solution:

 F = (λ a b c . (a b (a b c)))

Since that substitution makes a = b hold. My question is: what's an efficient (i.e., polytime) algorithm that solves this problem for as many cases as possible?

Maybe you should try nominal unification. In the paper nominal unification, it gives 4 examples which are untyped $\lambda$-terms.


Why is it best to use a prime number as a mod in a hashing function? If I have a list of key values from 1 to 100 and I want to organize them in an array of 11 buckets, I've been taught to form a mod function

$$ H = k \bmod \ 11$$

Now all the values will be placed one after another in 9 rows. For example, in the first bucket there will be $0, 11, 22 \dots$. In the second, there will be $1, 12, 23 \dots$ etc.

Let's say I decided to be a bad boy and use a non-prime as my hashing function - take 12.
Using the Hashing function

$$ H = k \bmod \ 12$$

would result in a hash table with values $0, 12, 24 \dots $ in the first bucket, $1, 13, 25 \dots$ etc. in the second and so on.

Essentially they are the same thing. I didn't reduce collisions and I didn't spread things out any better by using the prime number hash code and I can't see how it is ever beneficial.

Consider the set of keys $K=\{0,1,...,100\}$ and a hash table where the number of buckets is $m=12$. Since $3$ is a factor of $12$, the keys that are multiples of $3$ will be hashed to buckets that are multiples of $3$:

Keys $\{0,12,24,36,...\}$ will be hashed to bucket $0$.
Keys $\{3,15,27,39,...\}$ will be hashed to bucket $3$.
Keys $\{6,18,30,42,...\}$ will be hashed to bucket $6$.
Keys $\{9,21,33,45,...\}$ will be hashed to bucket $9$.

If $K$ is uniformly distributed (i.e., every key in $K$ is equally likely to occur), then the choice of $m$ is not so critical. But, what happens if $K$ is not uniformly distributed? Imagine that the keys that are most likely to occur are the multiples of $3$. In this case, all of the buckets that are not multiples of $3$ will be empty with high probability (which is really bad in terms of hash table performance).

This situation is more common that it may seem. Imagine, for instance, that you are keeping track of objects based on where they are stored in memory. If your computer's word size is four bytes, then you will be hashing keys that are multiples of $4$. Needless to say that choosing $m$ to be a multiple of $4$ would be a terrible choice: you would have $3m/4$ buckets completely empty, and all of your keys colliding in the remaining $m/4$ buckets.

In general:

  Every key in $K$ that shares a common factor with the number of buckets $m$ will be hashed to a bucket that is a multiple of this factor.

Therefore, to minimize collisions, it is important to reduce the number of common factors between $m$ and the elements of $K$. How can this be achieved? By choosing $m$ to be a number that has very few factors: a prime number.


Find equidistant triplets in a tree Given a tree $T$ with $n$ vertices, we want to find the number of triplets of vertices $(a,b,c)$ such $d(a,b) = d(b,c) = d(c,a)$ where $d$ is the distance function (length of the shortest path between two nodes).

It's pretty easy to do it in $O(n^3)$ time. Is it possible to do it faster?
I think that on-line algorithm and pre-processing should help.

Consider such a triplet $(a,b,c)$, and root $T$ at $a$. Let $e$ be the lowest common ancestor of $b$ and $c$. If $e = a$ then $d(b,c) = 2d(a,c)$, and we conclude that $a=b=c$. If $e \neq a$, then if we now root $T$ at $e$ then $e$ is the lowest common ancestor of $a,b,c$ (pairwise). That means that $a,b,c$ belong to different branches below $e$.

This gives rise to the following algorithm. First, there are $n$ triplets of the form $(a,a,a)$, which you may or may not want to count. Second, each triplet $(a,b,c)$ comes with its unique vertex $e$. So we enumerate over the vertices $e$, root $T$ at $e$, and for each child $f$ of $e$, count the number of vertices at any given depth; this takes time $O(n)$. Now for each depth $D$, we are given a list $a_1,\ldots,a_k$ corresponding to the number of vertices at depth $D$ for the children of $e$. We want to compute
$$ \sum_{i<j<k} a_i a_j a_k = \frac{1}{6} \left(\sum_i a_i\right)^3 - \frac{1}{2} \left(\sum_i a_i^2\right) \left(\sum_i a_i\right) + \frac{1}{3} \sum_i a_i^3.$$
This phase can also be accomplished in $O(n)$ (going over all possible depths), with some care (you need to sort the children according to depth, but that can be done in linear time since the depths are integers from $0$ to $n-1$; other details left to you). Therefore the entire algorithm is $O(n^2)$.

My guess is that you can find the number of triplets in $\tilde{O}(n)$.


Are different assignments allowed for the implication graph proof of 2-SAT being in P? One proof for $2-SAT$ being in $P$ uses the implication graph, i.e. one creates 2 vertices per variable $a$, one for each possible literal ($a$ and $\neg a$). One then adds 2 arcs per clause $(a \lor b)$, one from $\neg a$ to $b$ and one from $\neg b$ to $a$, respectively representing the implications $\neg a \implies b$ and $\neg b \implies a$. Finally, (assuming a solution exists) one sorts the connected components in topological order and traverses these in reverse order. Now for the important part :
For every literal $a$ encountered, set variable $a = true$, and for every literal $\neg a$ encountered, set variable $a = false$.
Don't change variables already set. The resulting assignment is a solution.
My question is : Do other assignments work as well, as long as the underlying implications stay $true$ ? For example :
For every literal $a$ encountered, set variable $a = false$, and for every literal $\neg a$ encountered, set variable $a = true$.
since $false \implies false$, or even some combination :
For every literal $a$ encountered, if it points to some literal that equals $false$, set $a = false$, otherwise set it to either $false$ or $true$. For every literal $\neg a$ encountered, if it points to some literal that equals $false$, set $a = true$, otherwise set it to either $false$ or $true$.
since $true \implies true$, $false \implies true$, and $false \implies false$?

You have to understand that $a \implies b$ cannot be interpreted as $\neg a \implies \neg b$. Only the contraposition $b \implies a$ is true, but this one is already in the implication graph by construction.
Thus, with your algorithm, you will make abrirtrary assignments. This will probably leads to an impossibility even if the problem does have a solution. Of course, on trivial examples, one can see that this algorithm may produce a solution.
Also note that  $a \implies b \implies c$ means there is elsewhere in the graph $\neg c \implies \neg b \implies \neg a$. So when you decide to assign false in order to $a, b, c$, you are reading the graph and the strongly connected components reversly.


How to find the loop invariant in hoare triples Hey I am new to Hoare triples, and I can't understand on finding the loop invariants in hypothesis. For example this while loop

[x>1 & y>1] WHILE x>0 DO x:=x-1; y:=y+2 END [x+y>5].

The invariant is [2x + y > 5] but I don't understand on how to find it. A step by step explanation on how to find it will be greatly appreciated.

First understand the meaning of the loop invariant. It means a condition which is true in every iteration of the program/algorithm at the begining as well as at the termination of the loop. Your program is something like this.

$$ x > 1 \text{ and } y >1 $$

$$\text{ While } x >0  $$

$$\hspace{4cm}\text{ Do } x:= x - 1, y:=y+2$$

$$\text{ End }$$

$$x + y > 5$$

$2x+y >5$ is an invariant as you described. It is visible from the program that both $x$ and $y$ will be greater than $1$ during the first iterataion of the loop. So in the first iteration of while loop $2x+y > 5$(you can prove it). Notice in each iteration of the while loop the value of the $x$ gets decrease by value $1$ and value of y is getting increase by two so inequality $2x+ y  >5$ will be satisfied. You can prove it. Now come to the termination condition, at this point $x$ will be a negative number and my claim is value of $y$ is going to be at least $5$. Thus the invariant $2x+y > 5$ si true throught the iteration of the while loop.

Example :

Let $x=2$ and $y=2$, then $2 \times 2+2 = 6 > 5$ is satisfied. Now in the second iteration  $x = 1, y=4$ so $1 \times 2+4 > 5$ satisfied. Now $x = 0, y = 6$, loop terminated, $2 \times 0+6 > 5$.


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

$$
    \begin{align*}\tag{P1a}\label{P1a}
      & {\underset{\mathbf{ x }, \mathbf{ y }}{\text{minimize}}}
      & & \sum_{j=1}^nf_jy_j\\[3pt]
      & \text{subject to}
      & & \sum_{i=1}^{m} w_{i}x_{ij} \leqslant C_{j}y_j,\forall\,j\in\{1,\dots,n\}\tag{P1b}\label{P1b}\\[3pt]
      & & & \sum_{j=1}^n x_{ij}=1, \forall\, i \in\{1,\dots,m\}\tag{P1c}\\[3pt]
      & & & x_{ij}, y_j \in\{0, 1\}, \forall\, i\in\{1,\dots,m\}, j\in\{1,\dots,n\}\tag{P1d}.
    \end{align*}
$$

The problem \eqref{P1a} can be found for example in variable sized bin packing problem.

The problem \eqref{P1a} can be seen as:

We have set of bins $\{1,\dots,n\}$ each with a weight $f_j$, a set of items $\{1,\dots,m\}$ each with a weight $w_i$. For each bin $j$, there is a capacity $C_{j}$.
We would like to assign all items to the bins such that every item is assigned to exactly one bin and the weights of items assigned to bin $j$ does not exceed the capacity $C_{j}$.

I am curious about the case where the weights of the items are all equal, say $w_i=1$ for all $i$. Can we derive an optimal algorithm in this case or it is still NP-hard?

I can't find an NP-hardness reduction but I think that we can do this algorithm:

sort the bins by $C_j$ in decreasing order;
start with bin 1, fill it with items until $C_1$ is reached;
go to the next bin and loop.

I have tried this algorithm with few examples but I cannot prove its optimality though.

Could you help please?

I'll change the description to avoid artificial sums.

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

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

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

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


Language member explanation Given the following formal language $L$:

$$    L=\{ww \mid w\in\{a,b\}^*\}$$

Why is $a$ not a member of this language?

So what is $\{a,b\}^*$ exactly? I thought it means $(a+b)^*$?

The notation $\{a,b\}^*$ stands for all strings over the alphabet $\{a,b\}$. A word is in the language $L$ if it is of the form $ww$, where $w$ is an arbitrary word over the alphabet $\{a,b\}$. For example, taking $w = aba$, we see that $abaaba \in L$. If $w$ has length $n$ then $ww$ has length $2n$, and in particular every word in $L$ has even length. So $a \notin L$. But this idea isn't enough to prove that $ab \notin L$.

If $x$ is a word of odd language, then $x \notin L$. If $x$ has length $2n$, then write $x=yz$, where $y$ consists of the first $n$ characters, and $z$ consists of the last $n$ characters. Then $x \in L$ if and only if $y=z$. If $x=ab$ then $y=a$ and $z=b$ and so $y \neq z$, implying $ab \notin L$.


Out of these two algorithms. Is there always an input where A is faster then B? (Big theta notation) I am currently learning landau notations and am stuck on the following True/False question.

What seems a little confusing to me is the use of big-theta notation to describe worst-case run-time.
What is the difference in saying "worst-case run-time Θ(n log n)" or simply "run-time O(n log n)"? Giving the worst case a tight limit seems a lot like simply giving an upper bound to the run-time.

If I go by that reasoning my guess would be that the statement is true. As an O(n) algorithm will be faster than an O(n log n) as n grows large enough.
But i am not sure if my reasoning is correct and if i get the big picture here.

Θ(n log n) means the algorithm is O(n log n) and Ω(n log n), and is slower than Θ(n) so your reasoning is correct.

But there's another layer: Landau notation denotes asymptotic bounds on functions. Saying "worst case" restricts it to those functions which result in the highest run time. For example take binary search: we get a best-case runtime asymptotic of Θ(1) and a worst-case asymptotic of Θ(log n).

To answer your question about the difference between "worst-case Θ(n log n)" and "run-time O(n log n)"*, the first one gives us more information: it tells us it runs about as fast as n log n, where the second tells us it runs at most n log n.

*Technically the second one doesn't tell us for what 'run-time' configuration it is asymptotically approaching, but in that case generally most people mean 'in the worst case this algorithm runs in O(n log n)' when they don't say anything.


Why can humans solve certain "undecidable" problems? High-order pattern matching is an undecidable problem. That means there is no algorithm that, given an equation a => b, where a and b are open terms on the simply typed lambda calculus, finds a substitution S such that aS => bS, where => stands for "has the same Bn normal form". Yet, humans can solve that problem efficiently. For example, given the following problem:

a = (λt . t
    (F (λ f x . (f (f (f x)))))
    (F (λ f x . (f (f x)))))
b = (λ t . t
    (λ f x . (f (f (f (f (f (f x)))))))
    (λ f x . (f (f (f (f x))))))

Any human with sufficient knowledge on the lambda calculus will be able to notice F is the "double" function for church numbers, quickly coming with the solution that

 F = (λ a b c . (a b (a b c)))

My question is: if that problem is undecidable, how can humans quickly and effortlessly solve it?

Humans can solve some instances of that problem efficiently, but there is no reason to believe that humans can solve all instances efficiently.  Showing one instance that a human can solve efficiently does not imply that humans can solve all instances efficiently.

Undecidable means "there is no algorithm that can solve all instances and that always terminates".  There could still be an algorithm that can solve some instances, even for an undecidable problem.

So there is no contradiction.


Data extaction vs information extraction How is information extraction related to data extraction? Is it a subfield or can it be used equivalently? Data is also information. What is the relation and what are the differences?

I want to write about the general topic "data extraction". I can hardly find papers about "data extraction", but most papers deal with "web data extraction", which I want to consider separately. Maybe someone can provide me some solid papers about "data extraction".

Of course, I had a look at https://en.wikipedia.org/wiki/Information_extraction and https://en.wikipedia.org/wiki/Data_extraction but this is not a reliable source. There must be more solid information about that somewhere.

Information gives semantics e.g. the meaning to data.  Consider pulling out of the tweets from the last hour as a raw data.    If you carry out sentiment analyses form this data you get something meaningful out of raw data: information about the mood of tweeters at the moment.

Data can be sourced by other means other than extracting.  For example apps can be developed to track information through sensors.  Imagine a sensor tracking movements in the wild, that would be raw data.  If you analyze the patterns of those movements you may infer the type of animal you have observed through the sensors e.g. information.

On a side note web extraction is possibly the most common way to extract data.
The only other common extraction scenario I can think of are ETL (Extraction and Transformation Loading) for Data-warehousing purposes using BI (Business Intelligence) tooling.


Problem with solving the recurrence $T(n) = 2T(\sqrt n) + \log n$ This question has already been asked before in this site, but the details of none of them is my question and none of them answer my question.
The following is an example recurrence given in introduction to algorithms book by CLRS .

$$T(n) = 2T(\sqrt n) + \log n$$

It is solved by changing the variables. It renames the $m = \log n$ and it yields

$$T(2^m) = 2T(2^{m/2}) + m$$

and it renames $S(m) = T(2^m)$, so it produces new recurrence

$$
S(m) = 2S(m/2) + m
$$

which is easy to solve.

I have two problems with this solution:

1- renaming $S(m) = T(2^m)$ must yield  $S(m) = S(m/2) + \log m$, since we can't change the argument of the $T$ and leave the $m$ as it was. We can use $S(m) = S(m/2) + m$ only if the original recurrence was $T(2^m) = 2T(2^{m/2}) + 2^m$

2- The second problem is, even if the above renaming is true, $2T(\dfrac{2^m}{2})$ would be $S(m/2)$ not the $2T(2^{m/2})$

thanks in advance.

Regarding your 1st problem:
You don't need to change $m$ to $\log m$. Let's suppose $f(x)=g(y)$.Then you do not need substitute $y$ anywhere. Because $y$ if substituted would again produce $y$. If you  substitute $y$, you must substitute  it by $g^{-1}f(x)$=$g^{-1}g(y)=y$. You can see you are again getting $y$.

Regarding your second problem:
$S(m)=T(2^m)$

Let $y=m/2$

$$S(y)=T(2^y)$$

$$S(m/2)=T(2^{m/2})$$

You must substitute $m$ by $m/2$. What you are doing is dividing $2^m$ by $2$ which is completely wrong.


If a language is m-reducible to a regular language, does it mean that this language is also necessarily a regular language? I've been going back and forth with this for a dew days, can't quite be sure.

When I look at the pumping lemma method, I think a context-free language could possibly be reduced to a regular language.

The answer to your question is no. There's a general result you can use in this case:

Theorem. If $A$ and $B$ are any decidable languages and $B\ne\varnothing$ and $B\ne\Sigma^*$, then $A\le_\text{M} B$.

This says that any nontrivial decidable languages are mapping reducible to each other. In other words, mapping reducibility tells you nothing about decidable languages.

Here's an example. Let $L=\{0^n1^n\mid n\ge 0\}$. This is a well-known non-regular language. Now let $R$ be, say the regular language $\{0\}$. Then $L\le_\text{M} R$ by the mapping $f:\{0, 1\}^*\rightarrow\{0, 1\}^*$ defined by
$$
f(s) = \begin{cases}
0\quad\text{if $s=0^n1^n$ for some $n\ge 0$}\\
1\quad\text{otherwise}
\end{cases}
$$
It's obvious that $f$ is Turing-computable and that $s\in \{0^n1^n\} \Longleftrightarrow f(s)\in R$, which is exactly what you need to show that this non-regular language is mapping reducible to this regular language.


Using approximations to optimization problems for threshold problems Many problems in computer science come in two flavors:

Optimization problem: "Find an object with the largest size".
Decision problem: "Given $n$, find an object with a size of at least $n$, or reply that such an object does not exist".

Given a solver for the optimization problem, the decision problem can be solved simply by checking if the optimal solution has a size of at least $n$. But this doesn't help if the optimization problem is NP-hard.

MY QUESTION IS: If we have a constant-factor approximation algorithm for the optimization problem, how can we use it for the threshold problem?

A possible way is: if the approximate solution has a size of at least $n$, return it; if it has a size of less than $n/c$ (where c is the approximation constant), return that an object of size $n$ does not exist; otherwise, return "I don't know".  This may return a correct answer in many cases, but not in all cases.

Is there a better way?

First off, a technicality: optimization problems aren't NP-complete; only decision problems can be NP-complete (or in NP).  Thus, it's only the decision problem (what you call the "threshold problem") that is in NP, or NP-complete.

On to the substance of your question.  The answer is: You can't.  In general, the approximation algorithm typically doesn't let you solve the decision problem.  Think about it.  We have many problems for where the decision problem is NP-complete, but where we have a polytime approximation algorithm.  If the approximation algorithm let us quickly solve the decision problem (or the corresponding optimization problem), then we'd immediately have a polytime solution to a NP-complete (or NP-hard) problem, and thus a proof that P=NP.  When you start with some assumption and it leads to a conclusion that is too good to be true, that's a sign that the assumption probably wasn't valid.

No, your "obvious answer" doesn't work.  Decision problems aren't allowed to return "I don't know".  No, there isn't a better way (assuming the problem is NP-hard, and assuming $P\ne NP$).


$Sat(EG^2\alpha)$ as a fixpoint of an operator Currently I am studying CTL model checking. I found this exercise:
Consider the CTL formula $EG^2(\alpha)$ which means that there exists a path that satisfies $\alpha$ at every even position. Define $Sat(EG^2(\alpha))$ as a fixpoint of an operator and describe how to extend the CTL model checking algorithm for formulas that contain the operator $EG^2(\alpha)$.

Let us prove that $EG^2\alpha$ is the greatest fixpoint of $\tau(Z):=\alpha\wedge EXEXZ$.
Suppose $s_0\in Sat(\tau(EG^2\alpha))$, then $s_0\in Sat(\alpha)$ and for some path starting at $s_0$, we have $s_2\in Sat(EG^2\alpha)$ where $s_2$ is a successor of $s_1$ and $s_1$ is a successor of $s_0$. That is, $s_0\in Sat(\alpha)$ and for some $\pi\in Paths(s_2)$, we have $\pi[2i]\in Sat(\alpha)$, $i\in \mathbb{N}$. Hence, $s_0\in Sat(EG^2\alpha)$.
Now, assume that $s_0\in Sat(EG^2\alpha)$, then for every $\pi\in Paths(s_0)$, $\pi[2i]\in Sat(\alpha)$, $i\in\mathbb{N}$. Therefore, $s_0\in Sat(\tau(EG^2\alpha))$.
We have seen that $EG^2\alpha$ is a fixpoint of $\tau(Z)$. Suppose, now, that $Y$ is a fixpoint of $\tau(Z)$, that is $Y=\tau(Y)$. Let us see that $Sat(Y)\subseteq Sat(EG^2\alpha)$. Let $s_0\in Sat(Y)$, then $s_0\in Sat(\alpha)$ and $s_2\in Sat(Y)$ for some $s_1\in suc(s_0)$ and $s_2\in suc(s_1)$. But then again $Sat(Y)=Sat(\tau(Y))$, so we have $s_0\in \alpha$, $s_2\in Sat(\alpha)$ and $s_4\in Sat(\alpha)$ for some $s_3\in suc(s_2)$ and $s_4\in suc(s_3)$. In the limit case, we get a path starting at $s_0$ that satisfies $EG^2\alpha$. Hence, $s_0\in Sat(EG^2\alpha)$.
To extend the CTL algorithm
$Sat(EG^2\alpha)$ is the largest $C\subseteq S$ ($S$ is the set of states) such that:

$C\subseteq Sat(\alpha)$;
$s\in C\Rightarrow\text{ for each }s'\in suc(s),\text{we have } suc(s')=C$.


Implement opposite() method to tell if there are two opposite numbers, (x,-x) Let a dictionary with the operations insert(), delete() and search(). Each one of them has time complexity of $O(logn)$. Implement (efficiently) opposite() operation which return true if there are two opposite numbers in the dictionary (i.e. $5$ and $(-5)$)

I advised to use another data structure.

I thought about a binary search tree. We maintain a binary search tree and for every insert() we also insert the item into the tree.

What do you think?

Here is what they intended you to do. You keep a counter of the number of opposite elements, which starts at zero. When inserting an element $x$, you insert both the true element $x$ and the dummy element $-x$; if $-x$ was already there, then you increase your counter of opposite elements. Similarly, when deleting $x$ you delete both $x$ and $-x$, and possibly decrease the counter.


Prove that a sequence of increasing find operations on a splay tree takes $\mathcal{O}(n)$ time When studying about splay trees, I found the following statement:

  Suppose we have a splay tree and a sequence of Find operations, where the elements we are searching for are in increasing order. Then the total time necessary to run the sequence is $\mathcal{O}(n)$ ($n$ is the number of nodes in the tree).

I looked around, but haven't been able to find anything. Can this be proven formally? Or shown that it is true?

Here is a helper fact.

(Simple cost of splaying) Let $c(v)$ be the time it takes to find an element $v$ in a splay tree. There exists a constant $c_0$ independent of the splay tree and $v$ such that $c(v)\le c_0d(v)$, where $d(v)$ is the depth of $v$.

Here is the sketch of a proof.

There are two tasks that contribute to $c(v)$.

To locate $v$ by going from the root downwards to the $v$, which takes at most $c_1d(v)$ time for some constant $c_1$.
To splay $v$ to the root. It takes each splay operation of zig, zag, zig-zig, zag-zag, zig-zag, zag-zig some constant time to move $v$ nearer to the root by 1 or by 2, splaying $v$ to the root takes at most $c_2d(v)$ time for some constant $c_2$.

Let $c_0=c_1+c_2$. Proof is done.

  Suppose we have a splay tree and a sequence of Find operations, where the elements we are searching for are in increasing order. Then the total time necessary to run the sequence is $O(n)$, where $n$ is the number of nodes in the tree.

Let $v_0, v_1,\cdots, v_m$ be an array of elements in increasing order.

It takes $O(n)$ to find $v_0$ (including splaying $v_0$ to the root).

What about finding the remaining $m$ elements?

Finding $v_1$ when $v_0$ is at the root takes at most $c_0d_{v_0}(v_1)$ time, where $d_{v_0}(v_1)$ is the depth of $v_1$ in the splay tree with $v_0$ as the root. Note that splay tree is a binary search tree, $d_{v_0}(v_1)$ is at most one one more than the number of elements between $v_0$ and $v_1$ exclusively.
Finding $v_2$ when $v_1$ is at the root takes at most $c_0d_{v_1}(v_2)$ time, where $d_{v_1}(v_2)$ is at most one one more than the number of elements between $v_1$ and $v_2$ exclusively.
$\vdots$
Finding $v_{m}$ when $v_{m-1}$ is at the root takes at most $c_0d_{v_{m-1}}(v_m)$ time, where $d_{v_{m-1}}(v_m)$ is at most one more than the number of elements between $v_{m-1}$ and $v_m$ exclusively.

So, the total time necessary to run the sequence of finding $v_1, v_2,\cdots,v_m$ is at most $c_0d(v_0, v_m)$, where $d(v_0, v_m)$ is at most one more than the number of elements between $v_0$ and $v_m$ exclusively, i.e., $d(v_0, v_m)\le m\lt n$.

So the total time necessary to run the sequence of finding $v_0, v_1, v_2,\cdots,v_m$ is at most $O(n) + c_0n$, which is $O(n)$ still.


How to find vertices of bounded region made by intersection of lines Suppose we have random lines made with 2 points. and point has (x,y)
For example:

Now when we draw a random line you will see many lines intersect with each other. This eventually gives rise to bounded regions. How to find the vertex points for each bounded region?
My approach:
First we find all the intersection points of the various lines. In some cases multiple lines intersect at the same point.
However I am not sure how to pick the points that make up a bounded region.
Thanks in Advance.

Finding the all the vertices for all of the bounding regions is roughly the same amount of work as creating a doubly connected edge list (DCEL) that represents your regions, so I will show how to construct a DCEL from a set of line segments. After that, finding all the boundary points for each region from a DCEL is a simple operation.

First, we find all line segment intersections between the segments we start with. This can be done efficiently with the standard sweepline algorithm for line segment intersection, which is described in various references, such as in these slides. This can be done in $O(n\log n + K)$ time, where $n$ is the number of line segments and $K$ the number of intersections between these lines.

For the next part, we construct a set of endpoints $P$ and a set of line segments $L$, where for each segment $l\in L$, we also store the pair of points $(p,q)$ from $P$ that are the endpoints of segment $l$. First, add all original line segments to $l$ and the corresponding endpoints to $P$.

Then, at every intersection point $p$, split the segments that intersect at that point into two segments 'separated' by $p$, store the point $p$ in the set $P$, remove the old segment from $L$ and add the new segments to $L$, setting their endpoints accordingly.

In the end, we have represented our regions with a graph $G=(P,L)$, where the vertex set $P$ are all points in our 2D space (including the intersection points) and the set of edges $L$ contains all segments connecting these points. Note that the graph $G$ doesn't have any crossing edges by construction, so it is planar.

From this planar graph, we can construct a DCEL, as shown in this answer, which is mostly bookkeeping.

In the DCEL, each region is associated with a representative half-edge. From that half-edge, we can find all half-edges that form the border of the region. Then, the vertices of the region are all vertices of those half-edges.

It is possible to skip the DCEL and find the vertices directly, but likely you need to do almost the same thing. The main advantage of using a DCEL as an intermediate step is that someone else already has made an algorithm to construct a DCEL.


Conditions for maximum period of quadratic congruential method (PRNG) $X_{n} = (d^2X_{n-1} + aX_{n-1} + c) \operatorname{mod} m$

Knuth lists out the necessity and sufficiency of 4 conditions (Exercise 8 in page 49 of "The art of computer programming Vol.II"):

  $c$ is relatively prime to $m$
  $d$ and $a-1$ are both multiples of $p$, for all odd primes $p$ dividing $m$
  $d \equiv a-1$(mod 2) when $2|m$; $d$ is even and $d \equiv a-1$(mod 4) when $4|m$
  $d \not \equiv 3c$ (mod 9) when $9|m$

Knuth writes in the answer to exercise 8:

  If $p \leqslant 3$, it's easy to establish the necessity of condition (iii) and (iiii) by trial and error method

I do try to find my own way to prove (the necessity of) condition (iii) and (iiii). Here's how i prove the first one:

Assume $m=p^e$. Firstly, we consider the case when $p=2,e=1$

So, the sequence $X_n$ with ($X_0 = 0$ and $m=2$) has the period of $2$ when:
$$X_2 = X_0 = 0 $$

We can prove: $X_2=dc+a+1 \operatorname{mod}$ 2 (due to the relatively prime $c$)

Obviously, we have: $$d \equiv a-1 (\operatorname{mod} 2)\space \tag1$$

If $e \geqslant 2$ then $4|m$. The same sequence $X_n$ with $(X_0=0,m=4)$ must have the period of 4 which means: $X_0\not=X_1\not=X_2\not=X_3$

$X_2 \not=X_0$. So, $X_2 = 2$ and $X_3 \not=X1$. The fact then implies:
$$aX_2 \not\equiv 0 (\operatorname{mod} 4)\space\tag2$$

Due to (1), (2), $a \operatorname{mod} 4$ and $d \operatorname{mod} 4$ can only adopt odd and even values. After some trials on $X_2 = dc + a + 1 \operatorname{mod} 4= 2$ (c is odd), we easily prove: $d \equiv a-1(\operatorname{mod} 4)$

I have also proved the condition (iiii) by my "trial and error method" but i'm not sure if they are what Knuth mentions. So my first question:
1. What's exactly "trial and error method" applying for this situation?

Finally, the proof of condition (ii) confuses me:

  If $d \not\equiv 0(\operatorname{mod} p)$ then $dx^2+ax+c \equiv d(x+a_1)^2 + c_1(\operatorname{mod} p^e)$ for some integers $a_1$, $c_1$ and for all integers x

$d\not\equiv 0 (\operatorname{mod} p)$ leads to d relatively prime to $p^e$. But i can't go on any further from this.

Why does $dx^2+ax+c\equiv d(x+a_1)^2 + c_1(\operatorname{mod} p^e)$ hold when $d \not\equiv 0(\operatorname{mod} p)$ ?

What's exactly "trial and error method" applied in this situation?

$\newcommand{\mymod}{\operatorname{modulo}}$As I understand, "trial and error method" here means checking all cases from a few simple natural or known perspectives until we have found a satisfactory solution or proof. It is useful and efficient in this situation because the number of cases $\mymod 2$ or $\mymod 4$ or $\mymod 9$ is very small.

What you have done seems pretty good.

  Why does $dx^2+ax+c\equiv d(x+a_1)^2 + c_1(\mymod{p^e})$ hold when $d \not\equiv 0\,(\mymod{p})$ ?

Prime $p\not=2$ since it has been assumed $p\ge5$. Since $d \not\equiv 0\,(\mymod p)$, $2d$ and $p^e$ are relatively prime, which implies $2d$ is invertible $\mymod p^e$. Let $(2d)d'\equiv1\,(\mymod p^e)$ fro some $d'$. Then

$$\begin{aligned}
dx^2+ax+c
&\equiv dx^2+2dd'ax + c\\
&\equiv d(x+d'a)^2 -d(d'a)^2+c\ (\mymod p^e)\\
\end{aligned}$$

Letting $a_1=d'a$ and $c_1=-d(d'a)^2+c$, we are done.


How can I convert a list with duplicates into a set for a reduction to the set cover problem? I'm trying to come up with a reduction for a problem whose description is more or less identical to the first problem given here.

Here's a condensed version of the problem:
You're given a collection of refrigerator magnet letters that may contain duplicates. You have a limited vocabulary of words made of combinations of those letters (again, a word may contain the same letter twice). Can you choose words from the vocabulary to build with the magnets such that all of the magnets are used and each magnet is used in only one word?

It's suspiciously similar to the set cover problem, so I've been trying to come up with a way to convert (in polynomial time) a collection of symbols that potentially contains duplicates into a set. This would allow the collection of symbols to be used as U and the child's vocabulary to be used as S for set cover.

I've had no luck so far, so a hint or even a suggestion for a more appropriate NP-complete problem to reduce to would be greatly appreciated.

There are several possible interpretations of the problem:

The alphabet size could be fixed or unbounded.
Words could be repeated or not.
The input histogram (how many letters of each type) could be encoded in unary (e.g., the letters are "aabcccccc") or in binary (e.g. $a\times 2, b\times 1, c \times 4$).

Here is the complexity of some of these variants.

Fixed alphabet, words may not be repeated, histogram is encoded in unary. Use dynamic programming. Given the list of words $w_1,\ldots,w_n$, compute inductively all possible histograms of all possible subsets of $w_1,\ldots,w_i$ which are "within budget". If the budget is $b_1,\ldots,b_m$ (so the alphabet size is $m$), then the number of such histograms is at most $(b_1+1)\cdots(b_m+1) \leq (2\max b_j)^m$, which is polynomial in the input size. Check whether the budget is one of these possible histograms.

Fixed alphabet, words may be repeated, histogram is encoded in unary. A similar strategy works, using a fixpoint iteration. Maintain a list of reachable histogram. At each round, add all words to all reachable histograms under budget, and update the list. Stop when the list stabilizes. Check whether the input histogram is one of them.

Unbounded alphabet. NP-complete, by reduction from 1-in-3 SAT. There is one letter per variable and clause, and one word per variable truth assignment. The word contains the variable symbol as well as the clauses satisfied by the assignment. All budgets are $1$.


Advantage of MTZ problem formulation of TSP In class, we saw the Miller-Tucker-Zemlin formulation of the Travelling Salesmen Problem (TSP).  MTZ is a way of formulating the TSP as an integer linear programming instance.

I understand how MTZ works, but I'm confused why MTZ is considered a better algorithm for checking for sub-cycles and rejecting them as answers than just keeping a list of connected nodes.

I can imagine a look-up table of each node along with a corresponding boolean that defines whether a node is connected or not. Consequently, the running time of checking if a connection is valid would be O(1). If it isn't a run-time consideration, what is the reason that MTZ is preferred?

The MTZ is not an algorithm.   Miller-Tucker-Zemlin formulation is a method of formulating the Travelling Salesman Problem as an instance of integer linear programming.  This lets you feed the resulting integer linear programming instance into an off-the-shelf solver for integer linear programming, and let the solver solve it for you.

Remember that an instance of integer linear programming is a set of variables and linear inequalities.  Lookup tables are not allowed; the inequalities have to be linear (e.g., $5x_1 + x_2 \le 7$, but not $T[x_1] \le 5$).  Therefore, using lookup tables are simply not an option, if you want to use integer linear programming.

Alternatively, you could skip using an integer linear programming solver at all, and try to solve the Travelling Salesman Problem from scratch.  But good luck with that.  It's an NP-complete problem, so it is unlikely you'll be able to find an efficient algorithm to solve the problem.  (And just saying "use lookup tables" is not an algorithm.)

Bottom line: I think you have a confusion about how integer linear programming works, and what MTZ is.  MTZ is not an algorithm for the TSP.  Rather, MTZ is a way of describing the TSP in a format that you can give to an integer linear programming solver.  Lookup tables aren't an option, if you're using an integer linear programming solver.


design a strange data structure, is it possible? I need a FIFO QUEUE that can do Insert and Remove from Queue in amortized $O(1)$ but extract min in $O(log n)$. is it possible?
When just find min is important (not removing) there is lots of $O(1)$ solution for all operation.
Update: All given times is amortized cost.

Let us denote four data structure: $Q$, $PQ$, $R_Q$, and $R_{PQ}$. $Q$ is a FIFO queue. $PQ$ is a priority queue implemented using a Fibonacci heap. $R_Q$ and $R_{PQ}$ are hash-sets. $R_Q$ stores elements that have been removed from the queue but not removed from the priority-queue yet; $R_{PQ}$ stores elements that have been removed from the priority-queue but not the queue yet.
Our operations are insert, delete, and extract-min. For insert, we insert the element into $Q$ and $PQ$.
We implement delete and extract-min lazily. For delete, let x=Q.front().  If $x$ exists within $R_{PQ}$, that means it has been removed from the priority-queue already. We pop $x$ and remove $x$ from $R_{PQ}$. Then, we set x=Q.front() and try again. If $x$ is not within $R_{PQ}$, then this is the element we should remove. We pop $x$ and insert it into $R_Q$.
For extract-min, we essentially do the reverse. We take x=PQ.top() until $x$ does not exist within $R_Q$, and when it does we pop $x$ and insert it into $R_{PQ}$.
Time complexity for insert: $O(1)$ (since we are using Fibonacci heap)
Time complexity for delete: amortized $O(1)$ (hash-sets work in amortized constant, and all our operations are either the deletion or lazy extract-min deletions.)
Time complexity for extract-min: amortized $O(logn)$ (hash-sets work in amortized constant, all our operations are either the deletion or lazy extract-min deletions, but logn factor due to PQ)
Update Code (C++):
struct strange_ds{
    queue<int> q;
    priority_queue<int> pq;
    unordered_set<int> rq, rpq;

    void insert(int x){
        pq.push(x); q.push(x);
    }

    void delete_ele(){
        while(true){
            int t = q.front();
            if(rpq.count(t)){ //already removed from pq
                q.pop();
                rpq.erase(t);
                continue;
            }
            q.pop();
            rq.insert(t);
            return;
        }
    }

    int extract_min(){
        while(true){
            int t = pq.top();
            if(rq.count(t)){ //already remove from q
                pq.pop();
                rq.erase(t);
                continue;
            }
            pq.pop();
            rpq.insert(t);
            return t;
        }
    }
};

Note that the code uses a standard C++ priority queue, which is not a Fibonacci heap, but this can be straight-swapped in. Also, the code assumes that element values are unique, but this can be accounted for in the case that they are not (by associating elements with unique IDs).


how does the parallel radix sort work? I'm currently learning computer science, and there is a slide of notes brief described the parallel radix sort under data parallelism.

number 101 110 011 001 111 (1st bit)
order    2   1   3   4   5 (new order)
number 110 101 011 001 111 (2nd bit)
order    3   1   4   2   5 (new order)
number 101 001 110 011 111 (3rd bit)
order    3   1   4   2   5 (new order)
number 001 011 101 110 111

I roughly know how to sort it from lecturer's explanation, but how is it related to parallel computing to increase the performance?

There are many ways to do it. The following approach allows to fairly split work between many cores. I believe that it's used even in GPU implementations of radix sort, such as ones provided by Boost.Compute and CUDA Thrust.

I describe here one pass of LSD radix sort that distributes data into R buckets:

First stage: split input block into K parts, where K is number of cores sharing the work. Each core builds histogram for one part of data, counting how many elements from this part of data should go into each bucket: Cnt[part][bucket]++
Second stage: Wait till all cores finished the stage one, and then compute partial sums over counts, thus revealing an initial index of each bucket for every part of data. This is sequential algorithm.
Third stage: each core again process its own part of data, sending each element into position determined by Cnt[part][bucket]

In pseudocode the entire pass looks like:

parallel_for part in 0..K-1
  for i in indexes(part)
    bucket = compute_bucket(a[i])
    Cnt[part][bucket]++

base = 0
for bucket in 0..R-1
  for part in 0..K-1
    Cnt[part][bucket] += base
    base = Cnt[part][bucket]

parallel_for part in 0..K-1
  for i in indexes(part)
    bucket = compute_bucket(a[i])
    out[Cnt[part][bucket]++] = a[i]


Help with recurrence solutions We started learning recurrences and I am having trouble with some of the problems. Our professor is having us substitute in $n=2^m$ and $S(m)=T(2^m)$ then writing down equations and summing them all up. I understand the substitution part, but not how to simplify the end result.

One of the problems I am stuck on is $T(n)=2T(n/2)+n^3$ where $T(2)=c$, When I sub in $n=2^m$ and $S(m)=T(2^m)$ I get:

$S(m)=2S(m-1)+(2^m)^3$

$S(m-1)=2S(m-2)+(2^{m-1})^3$

...

$S(3)=2S(2)+(2^{3})^3$

$S(2)=2S(1)+(2^{2})^3$

$S(1)=c$

Now because there is a coefficient on the right side we have to multiply each equation by a power of 2 so we can sum them.

$S(m)=2S(m-1)+(2^m)^3$

$2*S(m-1)=2^2S(m-2)+2*(2^{m-1})^3$

...

$2^{m-3}*S(3)=2^{m-2}S(2)+2^{m-3}(2^{3})^3$

$2^{m-2}*S(2)=2^{m-1}S(1)+2^{m-2}(2^{2})^3$

$2^{m-1}S(1)=c*2^{m-1}$

So sum these and we get:

$S(m)=(2^m)^3+2*(2^{m-1})^3+2^2*(2^{m-2})^3+...+2^{m-3}(2^{3})^3+2^{m-2}(2^{2})^3+c*2^{m-1}$

And this is where I get stuck, how can I simplify this? I tried dividing by $(2^m)^3$ but that came out to a awful mess. The other two I'm having trouble with are $T(n)=16T(n/4)+n^2$ and $T(n)=7T(n/2)+n^2$ Any help would be appreciated.

Once you have $S(m) = 2 S(m-1) + 2^{3m}$, you can divide by $2^m$ and obtain :
$$\frac{S(m)}{2^m} = \frac{S(m-1)}{2^{m-1}} + 2^{2m}$$
Thus, setting $P(m) = \frac{S(m)}{2^m}$, you should be able to find $P(m)$, then $S(m)$.


Solve T(n)=T(√n)+ n using substitution method I am confused how to solve this recurrence equn. after a particular step (step involving ? in the picture)

(Plz help me solve the question with same method which I have used and correct if any of the steps are wrong!)

Attached is what I have done so far..

As you mention,
$$
T(n) = n + \sqrt{n} + \sqrt[4]{n} + \cdots,
$$
and the number of terms is at most $\log \log n$. Hence
$$
n \leq T(n) \leq n + \sqrt{n} \log\log n.
$$
This implies that $T(n) \sim n$.


Do the two huffman trees have the same corpus? Consider the following Huffman trees:

I was asked if those trees can have the same corpus. My answer was no, based on these calculations:

For the right tree:
$a_1 \le a_2$
$a_1 + a_2 \le a_5$
$a_3 \le a_4$
$a_1 + a_2 + a_5 \le a_3 + a_4$

For the left tree:
$a_1 \le a_2$
$a_3 \le a_4$
$a_1 + a_2 + a_3 + a_4 \le a_5$

Adding the last equations from each tree we have that:
$2a_1 + 2a_2 \le 0$ Which is a contradiction because frequency cannot be negative.

Nevertheless, I understood that there is a possibility that the two trees would have the same corpus. For instance, consider $1,1,1,2,3$.

So, where do my calculations go wrong?

Your inequalities are based on the assumption that the left child of an inner node is not bigger than the right child. However, this does not hold. (Note that the condition is violated for the root of the right tree.)

Instead we do know that whenever the algorith chose to unite two nodes, there were no nodes with smaller weight present. For the left tree we find:

$a_1$ ad $a_2$ were joined before $a_5$ was joined to another node, so
$$a_1 \leq a_5\text{ and }a_2\leq a_5.$$
We do not know, if $a_1$ and $a_2$ were joined before or after $a_3$ and $a_4$, but in case the latter pair was joined first, we find $a_1 \leq a_3+a_4$ and $a_2\leq a_3+a_4$. If the former pair was joined first, we find $a_1\leq a_3$, $a_2\leq a_3$, $a_1\leq a_4$, and $a_2 \leq a_4$. These inequalities imply those of the first case, so we can conclude that $$a_1 \leq a_3+a_4 \text{ and } a_2\leq a_3+a_4.$$

Can you go on from here?