The GSAT algorithm is, for the most part, straight forward: You get a formula in conjunctive normal form and flip the literals of the clauses until you find a solution that satisfies the formula or you reach the max_tries/max_flips limit and find no solution.
I'm implementing the following algor...
Is there an algorithmic approach to identify that dates given in a paragraph correlate to particular events (phrases) in the paragraph?
Example, consider the following paragraph:
In June 1970, the great leader took the oath. But it was only after May 1972, post the death of the Minister of S...
There is a reduction in Sipser's book "Introduction to the theory of computation" on page 286 from 3SAT to Hamiltonian path problem.
Is there a simpler reduction?
By simpler I mean a reduction that would be easier to understand (for students).
Is there a reduction that uses linear numb...
In the Stable Matching Problem, it states that there can exist cases where the $m$ list of men can be content with their decisions, yet the list of $f$ cannot when the algorithm is run with men's proposals.
From what I read, an unstable match occurs when $m$ and $f$ prefer each other to their cu...
Two-level scheduling is useful when a system is running more processes than fit in RAM: a lower-level scheduler switches between resident processes, and a higher-level scheduler swaps groups of processes in and out.
I find no other mention of two-level scheduling in Andrew Tanenbaum's book. Exer...
In a round-robin scheduler, adding a process multiple times to the process list is a cheap way to give it higher priority.
I wonder how practical an approach this might be. What benefit does it have over other techniques such as giving the process a longer time slice (benefit: less switching tim...
Consider an embedded filesystem that does little more than store files in a hierarchical directory structure. This filesystem does not allow any kind of hard link or soft link, so every file has a unique name. Is there any benefit to storing a link to the directory itself and to its parent in the...
Is there an algorithmic approach to identify that dates given in a paragraph correlate to particular events (phrases) in the paragraph?
Example, consider the following paragraph:
In June 1970, the great leader took the oath. But it was only after May 1972, post the death of the Minister of S...
There is a reduction in Sipser's book "Introduction to the theory of computation" on page 286 from 3SAT to Hamiltonian path problem.
Is there a simpler reduction?
By simpler I mean a reduction that would be easier to understand (for students).
Is there a reduction that uses linear numb...
