Finding minimal and complete test sets for circuits I have been playing around with analysis of circuits and am trying to generate test vectors. In order to exercise the circuit in the manner I require, I need a vector that includes every change in the circuit's inputs where only 1 input toggles, but in order to be efficient, it must include each change only once and must not include any changes where more than one input toggles. Inputs can be only logic high (1) or low (0). If these sequences don't already have a name I would like to call them Majella tuples.

I believe the length of these Majella tuples to be    ((2^n) * n) + 1    where n is the width of the input in bits.

for example (with all 0 starting patterns):

n = 1:

0
1
0

n = 2:

00
10
11
01
11
10
00
01
00

n = 3:

000
100
110
010
110
111
011
001
101
001
011
111
101
111
110
100
101
100
000
010
011
010
000
001
000

I have written a bit of code to brute force generate these codes. However, it starts to struggle at n = 5 (actual code in a prev. revision of this question).

FUNCTION gen
  IF height of stack == ((2^bit_width) * bit_width)
    PRINT ZERO_PATTERN
    RETURN TRUE
  IF the change between the value at the top of stack and value does occur between other values on the stack
    RETURN FALSE

  PUSH value to stack
  WHILE shift < bit_width
    IF RECURSE with value as (value XOR (1 << shift)) returns TRUE
      PRINT value
      RETURN TRUE
    shift = shift + 1
  RETURN FALSE

SET stack to an empty list
SET bit_width to n

CALL gen with value as 0

some properties:

I would guess that there are solutions for all every possible n (positive integers). If there is a solution for n, there must be at least n! solutions as swapping the order of the inputs does not invalidate the solution. Reversing the order of a solution also does not invalidate it.

In each solution each input pattern should be present n times (except the starting pattern, that is present n + 1 times). The start and end patterns will always be the same.

Unfortunately this is where my knowledge runs out.

Is there a more efficient way of producing a valid solution given n as an input?

Can it be (easily) proven that there are solutions for all values of n?

edit:

I think it can be viewed as a graph:

   n = 2                   n = 3

                             000
    00                      / | \
   /  \                    /  |  \
  01  10                100  010  001
   \  /                  | \/   \/ |
    11                   | /\   /\ |
                        110  101  011
                           \  |  /
                            \ | /
                             111

The sequence is required to traverse each edge in both directions, but in neither direction more than once.

Yes.  One can construct a Majella sequence of length $n \cdot 2^n + 1$, recursively.  It's easy to see you can't do any better than this, so this is optimal.

Definition. I'll say that a sequence $x_0,x_1,\dots,x_m$ of $n$-bit values is a $n$-bit Majella sequence if $x_0=x_m$, and for each $y \in \{0,1\}^n$ and each value $e \in \{0,1\}^n$ with a single bit set, the pair $y,y\oplus e$ appears (consecutively) somewhere in the sequence.

Recursive construction. Let $w_0,w_1,\dots,w_m$ be a $n-1$-bit Majella sequence (for $n-1$-bit values).  Consider the following sequence:

$$0w_0, 0w_1,\dots, 0w_{m-1}, 0w_m, 1w_m, 1w_{m-1}, \dots, 1w_1, 1w_0, 0w_0,$$

where $0w$ represents the concatenation of $0$ and $w$.  This sequence is not yet a Majella sequence, but we can modify it to be one.  In particular, for each value $w \in \{0,1\}^{n-1} \setminus \{w_0\}$, replace the first occurrence of $0w$ in the sequence with $0w,1w,0w$ (increasing the length of the sequence by 2).

After this modification, the result is a $n$-bit Majella sequence.

This construction is inspired by the standard recursive construction of a Gray code, but tweaked slightly to satisfy your particular requirements.

Length of the recursive construction.  Let $L(n)$ be the length of the resulting sequence (i.e., the value of $m+1$).  It satisfies the recurrence relation

$$L(n) = 2L(n-1) + 2^n - 1$$

with $L(1) = 3$.  This solves to

$$L(n) = n \cdot 2^n + 1.$$

Algorithms. I don't know if there are any efficient, low-space algorithms for enumerating through such a sequence, like there are for Gray codes.


Number of logic gates for "reasonable" Turing completeness Somewhere on stackexchage, I, or someone else asked what was the proper term for Turing completeness minus the infinite memory (e.g. a Turing machine that one can actually build, no bigger than your typical data center).  Answer was inconclusive.

Also, someone else asked somewhere else on stackexchange about the number of gates for a Turing machine, but that got sidetracked into the useless infinite definition (that many quanta do not exist in the known universe).

So using the non-infinite Turing machine definition (*), whatever that is, is there a known lower bound on the number of 2-input binary gates needed to produce a Turing complete computer?  Or a reasonable guess or a minimum among known current published existing example implementations?

(* If necessary assume the "tape" is external to the logic gate count, the gates just drive the tape read/write/move mechanism).

As soon as you limit "memory" you are talking about machine models that are equivalent to finite automata. If you limit "memory" to input size, you are at linear bounded automata, which are easily seen to be limited to recognizing (some) recursive sets.


Class of languages that are equivalent to the lambda calculus It is well known that all computable functions can be expressed as terms of the lambda calculus and computed according to its rules. It is also more or less obvious that many classical formal languages (i.e. languages with formalized semantics) can be translated into the lambda calculus (e.g. using a Church encoding). I am, however, pretty sure that there are languages where such a translation is not possible, the simplest example would be a language with a builtin primitive that solves the Halteproblem.

That makes me wonder if there is an established terminus for the languages that can be translated.

Is there a name for the class of languages that can be translated (correctly, completely) into the lambda calculus?

The lambda calculus is exactly equivalent in expressive power to Turing machines, so the languages that can be translated into it are exactly those that are no more powerful than Turing machines.

Models of computation that are more powerful than Turing machines are known as "hypercomputation". However, except for computability theorists, most people don't ever consider languages that can express hypercomputation, so most people don't need a word that "not capable of hypercomputation." It's a bit like there being no word for "food that isn't poisonous" because not being poisonous is the default state for food so people don't really need a word for that.

Your question title asks about languages that are equivalent to the lambda calculus, i.e., those where we can translate in both directions. Because the lambda calculus has the same power as Turing machines, these are exactly the Turing-complete languages.


Winning strategy of Nim game when picking from multiple piles is allowed I am studying with Game theory right now. In Nim game, in any turn, a player can move any number of stones from any one pile. I am wondering what might be the winning strategy of first player if in any move, a player can pick any number of stones from one or more piles? In this case, how the xor = 0 rule will work? Both are playing optimally.

The answer assumes that you have to take the same amount of stones from each pile that you choose. Otherwise the first player always wins as long as the piles are not all empty.

The rule "xor = 0" doesn't work. In particular, there is a winning position with xor = 0 (easy exercise; be creative).

In order to analyze the game, you can compute which positions are winning and which are losing recursively (surely you have been shown how to do that in your course). Then you can look at which positions are winning and which are losing, and try to guess a rule; you will then need to prove that your rule works.

In this particular case, however, the analysis will be quite difficult. The case of two piles is known as Wythoff's game, and is already pretty non-trivial to analyze.


Lower-bound complexities for finding common elements between two unsorted arrays I'm facing some problems that deal with finding common elements between unsorted arrays and I'd like to know whether there are well-known lower-bounds for the worst-case and, eventually, what are these lower-bounds.

The problems are pretty simple:

  Given two unsorted arrays of distinct integers, $A$ and $B$, of size
  $m$ and $n$, determine all the common elements between the two
  arrays(the output must be sorted)

Which I believe has a lower-bound complexity of $\Omega((m+n)\log(\min(m,n)))$
(and $O(1)$ space complexity, if we exclude the input arrays),
even though I cannot find any proof of this fact. [I found an algorithm with this complexity, so I(hopefully) am not underestimating the complexity.]

The other problem adds some restrictions(and hence I'd expect to be able to lower the complexity):

  Given two unsorted arrays of distinct integers, $A$ and $B$, of size
  $m$ and $n$; knowing that common elements between the arrays have the
  same relative order in both arrays and that for every couple of
  consecutive common elements, their distance is at most $k$(constant),
  determine all the common elements between the two arrays maintaining
  their relative order and using at most $O(k)$ memory in addition to
  the input arrays.

I've tried to think about this second problem but I cannot see how the restrictions change the complexities. What puzzles me is that I believe that finding a single couple of elements between two unsorted arrays is $\Theta((n+m)\log(\min(n,m)))$, and since this is a special instance of this second problem then the restrictions do not add anything to the problem itself.

Are my guesses correct, and if so where can I find proofs for these lower-bounds? Do the restrictions change anything at all or the solution for the first problem is the best we can achieve in both cases?

Probably my questions can be summarized by the following:

  Given two arrays of distinct integers $A$ and $B$ of size $m$ and $n$,
  what is the lower-bound complexity for finding one common element?

Because, once a common element is found, the second problem can be solved in linear time.

Edit

The algorithm(s) that I thought are pretty simple:

For problem 1: Build two heaps for $A$ and $B$(which takes linear time and can be done in-place), then compare the minimum of the heaps, if they match print it and remove both, otherwise remove the smallest one and continue until the heaps are empty(this clearly takes $O((m\log(m) + n\log(n)) = O(\max(m,n)\log(\max(m,n)))$).

An other solution is to sort one array in-place, scan the other array and use bisection search to find matches. If we sort the smallest array (with size $m$) then the complexity is $O(m\log(m) + n\log(m)) = O(\max(m,n)\log(\min(m,n)))$. This technique yields the values in the other in which their are found in the biggest array, and it can be used to solve the second problem.

But, as you can see, I'm not using the extra restrictions at all and both algorithms use $O(1)$ space instead of $O(k)$(yes, it's still constant but $O(k)$ should give a bit more freedom).

For the first question, when $m = n$, you can get an easy $\Omega(n\log n)$ lower bound (in appropriate computation models) by taking $A = B$. More generally, following the method outlined here, it seems that (assuming $n \geq m$) you can get a lower bound of $\Omega(\log (m! \binom{n+1}{m})) = \Omega(n\log m)$ by considering the problem of Set Intersection. (In the proof of Theorem 4, fix the order of the $X$s, and vary the order of the $Y$s and their location.)

As for your algorithm, perhaps it modifies the input arrays? Perhaps this is not allowed in the intended computation model, in which the input is read-only, the work tape is read-write, and the output tape is write-only. (This is just a guess.) In any case, it will really help if you explained your algorithm.


Turing machine deciding $\{1^{2^n} : n \geq 0 \}$ How can I design a Turing machine that accepts the language $\{1^{2^n} : n \geq 0\}$?

Here is my attempt:

[![enter image description here][1]][1]

Here is the idea:

Go over the entire input, crossing out every other 1 encountered.

Reject if the number of 1s encountered was odd but more than 1.

Accept if the number of 1s encountered was exactly 1.

Otherwise, go back to step 1.


Confusion about assignment axiom in Hoare logic I wanted to know if we are given the f.f.g. Hoare triple:

{x = 43}x := x + 1{x = 44}

How do we show that this is a valid Hoare triple?

My attempt was:

Using the assignment axiom:
{x + 1 = 43} x := x + 1 {x = 44}

But this doesn'the make sense. I also want to know what went wrong in my attempt?

The assignment axiom in standard Hoare logic says:

|- {P[e/x]}x:=e{P}

If you choose P[e/x] to be x+1=44 (that is e is x+1) you get:

|- {x+1=44} x:=x+1 {x=44}

By the consequence rule, since:
|= x=43 --> x+1=44, and
|= x+1=44 --> x+1=44, and
|- {x+1=44} x:=x+1 {x=44}

you know that |- {x=43} x:=x+1 {x=44} .

By soundness:
|={x=43} x:=x+1 {x=44}


Why are functional languages Turing complete? Perhaps my limited understanding of the subject is incorrect, but this is what I understand so far:

Functional programming is based off of Lambda Calculus, formulated by
Alonzo Church.
Imperative programming is based off of the Turing machine model, made
by Alan Turing, Church's student.
Lambda calculus is as powerful and able as the Turing Machine,
meaning they are equivalent in computational power.

If functional programming is based off of Lambda Calculus and not the Turing machine, then why are some (or all) of them described to be Turing complete, and not Lambda complete or something like that? Is the term "Turing completeness" special in any way to Turing machines, or is it just a word?

Lastly, if imperative languages are based off of the Turing Machine, and computers are basically Turing machines, without infinite memory, does that mean they perform better than functional programming languages on our modern PCs?

If that's the case, then what would be the equivalent of a lambda calculus machine?

I know this seems to be 3 separate questions, but they're all closely related, and each is dependent on the previous question being a valid question to begin with.

In a nutshell:

What characterizes imperative programming languages as close to Turing
machines and to usual computers such as PCs, (themselves closer to
random access machines (RAM) rather than to Turing machine) is the
concept of an explicit memory that can be modified to store (intermediate results). It is an automata view of computation, with a concept of a
state (comprising both finite state control and memory content) that can change as the computation proceed.

Most other models are more abstract. Though they may express the
computation as a succession of transformation steps of an original
structure, these transformation are applied in a sort of intemporal
universe of mathematical meanings. This may preserve properties, such
as referential transparency, that may make mathematical analysis
simpler. But it is more remote from natural physical models that rely
on the concpet of memory.

Thus there are no natural functional machines, except in a larger sense
as explained below, since software is not really separable from
hardware.

The reference to Turing as the yardstick of computability comes probably from the fact that his model, the Turing machine was closest to this physical realizability constraint, which made it a more intuitive model of computation.

Further considerations:

There are many models of computation, which were designed to capture in
the most general possible way the concept of a computation. They
include Turing machines, actually in many different flavors, the
lambda calculus (flavors too), semi-Thue rewriting systems, partial
recursive function,
       combinatory logic.

They all capture some aspects of the various techniques used by
mathematicians to express or conduct computations. And most have
been used to some extent as the basis of some programming language
design (e.g. Snobol for rewriting systems, APL for combinators, Lisp/Scheme for lambda calculus) and can often be combined in diverse ways in modern programming languages.

One major result is that all these computation models were proved
equivalent, which lead to the Church-Turing thesis that no physically
realizable models of computation can do more than any of these models.
A model of computation is said Turing complete if it can be proved
to be equivalent to one of these models, hence equivalent to all of
them.

The name could have been different. The choice of the Turing machine
(TM) as the reference is probably due to the fact that it is probably
the simplest of these models, mimicking closely (though
simplistically) the way a human computes and fairly easy to implement
(in a limited finite form) as a physical device, to such an extent
that Turing machines have been constructed with Lego sets. The basic idea requires no mathematical sophistication. It is probably the simplicity and
realizability of the model that gave it this reference position.

At the time Alan Turing created his computing device, other proposals
were on the table to serve as formal definition of computability, a
crucial issue for the foundations of mathematics (see
Entscheidungsproblem). The Turing proposal was considered by the
experts of the time as the one most convincingly encompassing known
work on what calculability should be (see Computability and
Recursion, R.I. Soare, 1996, see section 3.2). The various proposals were proved equivalent, but Turing's was more convincing. [from comments by Yuval Filmus]

It should be noted that, from a hardware point of view, our computers
are not Turing machines, but rather what is called Random Access
Machines (RAM), which are also Turing complete.

Purely imperative language (whatever that might mean) are probably the
formalisms used for the most basic models, such as Turing machines, or
the assembly language (skipping its binary coding) of computers. Both
are notoriously unreadable, and very hard to write significant
programs with. Actually, even assembly language has some higher level
features to ease programming a bit, compared to direct use of machine
instructions. Basic imperative models are closed to the physical
worlds, but not very usable.

This led quickly to the development of higher level models of
computation, which started mixing to it a variety of computational
techniques, such as subprogram and function calls, naming of memory
location, scoping of names, quantification and dummy variables,
already used in some form in mathematics and logic, and even very
abstract concepts such as reflection (Lisp 1958).

The classification of programming languages into programming paradigm
such as imperative, functional, logic, object oriented is based of the
preeminence of some of these techniques in the design of the language,
and the presence or absence fo some computing features that enforce
some properties for programs or program fragments written in the
language.

Some models are convenient for physical machines. Some others are more
convenient for a high-level description of algorithms, it that may
depend on the type of algorithm that is to be described. Some
theoretician even use non deterministic specification of algorithms,
and even that cn be translated in more conventional programming terms.
But there is no mismatch problem, because we developed a sophisticated compiler/interpreter technology that can translate each model into another as needed (which is also the basis of the Church-Turing thesis).

Now, you should never look at your computer as raw hardware. It does
contain boolean circuitry that does very elementary processing. But
much of it is driven by micro-programs inside the computer that you
never get to know about. Then you have the operating system that makes
your machine appear even different from what the hardware does, On top
of that you may have a virtual machine that executes byte-code, and
then a high-level language such as Pyva and Jathon, or Haskell, or
OCaml, that can be compiled into byte code.

At each level you see a different computation model. It is very hard
to separate hardware level from the software level thus to assign a
specific computational model to a machine. And since they are all
intertranslatable, the idea of an ultimate hardware computation model
is pretty much an illusion.

The lambda calculus machine does exist: it is a computer that can
reduce lambda calculus expressions. Ad that is easily done.

About specialized machine architectures

Actually, complementing Peter Taylor's answer, and following up on
hardware/software intertwinning, specialized machines have been
produced to be better adapted to a specific paradigm, and had their
basic software written in a programming language based on that
paradigm.

These include

The Burroughs B5000 and its successors (1960s), that were adapted for
efficient implementation of recursion, represented at the time by
the language Algol 60.
The Western Digital WD/9000 Pascal MicroEngine, a machines based on
a microprogrammed bytecode specialied for the Pascal programming
language, in the early 1980s.
Several brands of Lisp Machines in the 1980s.

Fundamentally, these are also imperative hardware structures, but mitigated with
special harware features or microprogrammed interpreters to better
adapt to the intended paradigm.

Actually, hardware specialized for specific paradigms does not seem to
have ever been successful in the long run. The reason is that the
compiling technology to implement any paradigm on vanilla hardware
became more and more effective, so that specialized hardware was not
so much needed. In addition, harware performance was fast improving,
but the cost of improvement (including evolution of basic software)
was more easily amortized on vanilla hardware than on specialized
hardware. Specialized hardware could not compete in the long run.

Nevertheless, and though I have no precise data on this, I would suspect that these ventures left some ideas that did influence the evolution of machines, memories, and instruction sets architecture.


I'm lookin for a method to construct a particular grammar? I'm looking for an algorithm to construct a grammar which, given a set of words which can have multiple identical symbols, represents a compressed version of this set, that is, I can generate only the words of the set but the grammar will take less memory than the set himself.

Besides, I'm looking for an algorithm which can update the grammar when I want to remove a word of the set.

What type of algorithm is able to do that ?

I give a concrete example:

Consider a string S="abcdefghij", and then consider the finite set of words "cdhij", acdef", "fghi", "bcfgij", "defi".

I would like to construct a grammar which generates only this set of words (words which can be viewed as concatenation of various substrings of any length from the original string S).

Finally I would like to remove a word in the set and update subsequently the grammar.

Thank you.

it is not clear what you mean by "words which have multiple identical symbols". it sounds like you mean certain symbols are interchangeable. in that case, just replace all cases of an interchangeable symbol with a single representative symbol.

as to the more general question, there is an area of CS not-so-widely studied, called grammar based codes which is, roughly, focused on the idea of creating compressions of strings based on grammar expansions. in this way classic compression algorithms such as eg Lempel Ziv can be regarded as special cases of grammar compressions.

your problem is not so well defined unless you specify the type of grammar also, eg say CFG. if the grammar is generated by a recursive machine, then this problem is actually similar or almost identical to finding the Kolmogorov complexity of a string, which is undecidable in general.


How important is it to find a deterministic polynomial time algorithm to construct Ramanujan graphs? As in I don't know what is the difference between say the conferences SODA, STOC or FOCS. Measured in terms of such conferences, where would such a result be publishable?

This is not a "technical" question.
I want to understand how importantly does the community view this question if hypothetically someone does this.

May be you can just comment and not write an "answer"

There is already an explicit construction of Ramanujan graphs, due to Margulis and (separately) Lubotzky–Philips–Sarnak. Their construction only gives graphs with degree $p+1$ for some prime $p$. Later this was extended to cover prime powers $p$.

Recently, Marcus, Spielman and Srivastava gave a probabilistic construction of bipartite Ramanujan graphs of all degrees, and the paper appeared in FOCS 2013, and is due to appear in the Annals of Mathematics. This construction cannot even be implemented by an efficient probabilistic algorithm, and only works for bipartite graphs. In very recent work, the same authors extend their method to give bipartite Ramanujan graphs of all degrees and all sizes, in work that was submitted to FOCS 2015 (per Adam Marcus's homepage).

The community finds the recent line of work exciting not only because of the results themselves, but also because of the very interesting technique, which while (as far as I understand) not entirely new, has reached a new level of sophistication and applications. Improving on their results, either to get efficient algorithms or to remove the bipartiteness assumption, will likely require new techniques, and so will be exciting for the community.

While both papers mentioned above were submitted to FOCS, this is just due to coincidence; they might as well have been submitted to STOC. There is no real difference between these conferences, other than the time of year in which they take place, and the organization sponsoring them. SODA is considered less prestigious than FOCS and STOC.


invariant of bin packing We are given an array of integers and a number K. We need to pack these integers into bins. The condition is that we have to use exactly K number of bins and each bin should have equal capacity. We need to find the size of bin such that wastage of unused bin is minimized.

Is this problem polynomial time solvable?

Since the number of bins is fixed, the problems boils down to a job shop scheduling with atomic jobs. See https://en.wikipedia.org/wiki/Job_shop_scheduling#Atomic_jobs

A solution is given by $\max\{ 1/m \sum_{i=1}^n t_i, max_i t_i  \}$
where $t_i$ represents the $i$th integer and $m$ represent the set length. The wiki reference above includes a paper with the proof.

EDIT after request on polynomial time
Since it's equivalent to the partition problem, which is NP-hard, this problem is also NP-hard and therefore not solvable in polynomial time.


Example of a non-context free language that nonetheless CAN be pumped? So basically L satisfies the conditions of the pumping lemma for CFL's but is not a CFL (that is possible according to the definition of the lemma).

The classical example is $L = \{ a^i b^j c^k : i,j,k \text{ all different} \}$. Wise shows in his paper A strong pumping lemma for context-free languages that neither the Bar-Hillel pumping lemma nor Parikh's theorem (stating that the set of lengths of words in a context-free language is semi-linear) can be used to prove that $L$ is not context-free. Other tricks like intersecting with a regular language also don't help. (Ogden's lemma, a generalization of the Bar-Hillel pumping lemma, does prove that $L$ is not context-free.) He also provides an alternative pumping lemma which is equivalent to context-freeness (for computable languages), and uses it to prove that $L$ is not context-free.

Wise's pumping lemma states that a language $L$ is context-free if and only if there is an (unrestricted) grammar $G$ generating $L$ and an integer $k$ such that whenever $G$ generates a "sentential form" $s$ (so $s$ can include non-terminals) of length $|s| > k$, we can write $s = uvxyz$ where $x,vy$ are non-empty, $|vxy| \leq k$, and there is a non-terminal $A$ such that $G$ generates $uAz$ and $A$ generates both $vAy$ and $x$.

By repeatedly applying the condition in the lemma, Wise is able to prove that $L$ is not context-free, but the details are somewhat complicated. He also gives an even more complicated equivalent condition, and uses it to prove that the language $\{ a^n b a^{nm} : n,m > 0 \}$ cannot be written as a finite intersection of context-free languages.

If you cannot access Wise's paper (it's behind a paywall), there's a typewritten version which came out as an Indiana university technical report.

A non-context-free language which satisfies the pumping condition of Ogden's lemma is given by Johnsonbaugh and Miller, Converse of pumping lemmas, and attributed there to Boasson and Horvath, On languages satisfying Ogden's lemma. The language in question is
$$ \begin{align*}
L' &= \bigcup_{n \geq 1} (e^+a^+d^+)^n(e^+b^+d^+)^n(e^+c^+d^+)^n
\\ &\cup (a+b+c+d)\Sigma^* \cup \Sigma^*(a+b+c+e) \cup \Sigma^*(ed+d(a+b+c)+(a+b+c)e)\Sigma^*.
\end{align*} $$
We can write $L' = L_1 \cup L_2$, corresponding to the two different lines. Note that $L_1 \cap L_2 = \emptyset$ and that $L_2$ is regular. Ogden's lemma can be used to prove that $L_1$ is not context-free, and so neither is $L'$, but it cannot be used directly to show that $L'$ is not context-free.


Find the shortest string that is not a sub-string of a set of strings Alphabet: abc

Sample input:

abc
cba
aabbcc
aaabbbccc
caac

Sample good outputs: acb, cab, cac and others, since they are not substrings of any other, and because all strings of length 1 and 2 are present.

Sample bad outputs:

aab since it is a substring of 3)
aaaa because it is not minimal: we have other solutions with 3 characters only

Questions:

What are the best ways to solve it?
Does the problem have a well known coined name?
What is the complexity of the calculation in terms of the input size (number of strings N and maximum string length M)?
What is the average asymptotic size of the output considering random uniformly distributed inputs?

Related questions:

Algorithm Request: "Shortest non-existing substring over given alphabet" seems to be the case for a single input string. If we can find a trivial reduction we can close as a duplicate.

Applications:

for file uploads, browsers use the enctype='multipart/form-data' encoding. This encoding can send several files in a single HTTP request. Files are sent directly without character encoding, so to separate the files, the browser has to find a string that is not contained in any of the files. I'd like to know how that can be done optimally. See also: https://stackoverflow.com/questions/4526273/what-does-enctype-multipart-form-data-mean/28380690#28380690
apparently this has some interest for bioinformatics, although I know nothing about that domain: https://biology.stackexchange.com/questions/3064/shortest-strings-not-present-in-the-human-genome . There has been some discussion on that question, but the answers there are more heuristic than algorithmic.

Here's one possible solution, similar to the linked question: Algorithm Request: “Shortest non-existing substring over given alphabet”

Use a sliding window over each input string to build your trie.

For n=1 to n=max(length(s)) where s is an input string, do:
For each s, construct window of size n, slide window over s adding each window (substring of size n) to the trie, then
Visit each parent of the leaf set of the trie. If there exists a parent node whose set of child nodes is smaller than the size of the alphabet, then you can form your desired string from this parent by appending a character from the alphabet that does not result in a string identical to one of the leaf nodes
If no such parent node exists, continue to next larger n


How to find the largest power of two divisor of a given integer? Given an integer $x$, I need to find the largest power of two $p = 2^n$ that divides $x$ such that the remainder is zero.
When $x$ is zero, the algorithm should return zero. For odd numbers, it should return one, since the largest power of two that divides these numbers is $2^0$.
How to write an algorithm for this? (any programming language would do, or pseudocode)

You just need to count the number of $0$ at the end of the binary encoding of $x$.


Class of languages recognised by a Forgetful Turing Machine A Forgetful Turing Machine (FTM) operates just like a normal Turing machine except that, in every instruction (i.e., transition), the letter written in the tape cell is always the letter $a$, regardless of the current state and the current letter (although the read/write head is still allowed to move either Left or Right, according to the instruction). What class of languages is recognised by FTMs?

Is the language non-empty with only the letter $a$? Does this mean that it is regular since it can be represented by $aa^*$?

The class languages recognized by FTMs are the class of regular languages. A FTM can completely simulate a DFA, so each regular language can be recognized by a FTM. On the other hand, if we can prove each FTM recognizes a regular language, we have proved the assertion.

Given a FTM $F$ with the set of states $Q$, we use the Myhill–Nerode theorem to show the language it recognizes is regular. Given a string $x$, we ask the following query:

If $F$ runs on $x$, does $F$ ever leave $x$ to the right? If so, in which state is $F$ when it first moves to the first position to the right of $x$? If not, does $F$ accept $x$?

... and the following $|Q|$ queries for each state $q\in Q$:

If $F$ runs on $\underbrace{a\cdots a}_\text{the number of $a$ = $|x|$}$, but is started on the rightmost $a$ and in state $q$, does $F$ ever leave the input to the right? If so, in which state is $F$ when it first moves to first position to the right of the input? If not, does $F$ accept the input finally?

We collect the strings that give the same answers to the $|Q|+1$ queries above into the same class. Since there are $(|Q|+2)^{|Q|+1}$ possible answers to the $|Q|+1$ queries above, there are only finite many classes. Next, we are going to prove that for any strings $x,y$ in the same class, i.e., that give the same answers to the $|Q|+1$ queries, for any string $z$, $F$ accepts either both or neither of $xz$ and $yz$, which completes the proof by the Myhill–Nerode theorem.

Consider that $F$ runs respectively on $xz$ and $yz$. Note the answers to query 1 are the same for $x$ and $y$, there are two cases:

$F$ never leaves $x$ to the right on $xz$, and $F$ never leaves $y$ to the right on $yz$. In this case, $F$ runs as if the inputs are respectively $x$ and $y$. Since the answers to query 1 are the same for $x$ and $y$, $F$ accepts either both or neither of $xz$ and $yz$.
$F$ ever leaves $x$ to the right on $xz$, and $F$ ever leaves $y$ to the right on $yz$. In this case, $F$ is in the same state when it first moves to the leftmost position of $z$, so $F$ behaves the same until it returns respectively to the rightmost position of $x$ and $y$. According to the definition of FTM, the input must become $a\cdots a$ when $F$ returns, and we can apply a recursive analysis according to query 2 (you can use mathematical induction to write a strict proof). As a result, $F$ accepts either both or neither of $xz$ and $yz$.

Of course, the analysis above assumes the tape of the FTM is restricted such that the head cannot leave the input to the left. The proof is similar without this assumption.


Approximate Subset Sum with negative numbers I am interested in the approximation version of the Subset Sum problem with negative numbers.
Wikipedia says there is an FPTAS algorithm for SS. That Wikipedia page states:

  If all numbers are non-negative, the approximate subset sum is solvable in time polynomial in N and 1/c.

Similarly, in the CLRS version of the algorithm, the numbers are required to be positive. For the exact version there is this reduction that makes
all numbers positive but I believe that it cannot be applied to the
approximation version.
Because the approximation algorithm behaves differently for larger numbers it would not give the same results if instead of -10 I have 10000. The trim function would cut a lot more numbers
in the new, all positive version than in the original.

My question: Is there a FTPAS for General-SS, as defined below?

General-SS:
Given an input set $S=\{a_1,\dots,a_n\}$, where $a_i$ are possibly negative numbers, and a target $C$ find a subset $S'\subseteq S$ that sums to $C$.

All-positive-SS (defined below) has an FTPAS. Does this algorithm remains an FPTAS for General-SS?

All-positive-SS:
The same as General-SS, but where we restrict $a_i\geq 0$.

Alternatively, if we transform General-SS to All-positive-SS with
the above reduction and then run the FPTAS algorithm for the new instance, does this also give an FTPAS for General-SS?

I believe the issue is with the definition of approximation.

Let's assume that we want to find a subset that sums to $C=0$.  Then the approximate subset sum problem determines whether or not there is a subset within $(1-c)C$, which is just $0$.
Thus "approximate" subset sum is exactly subset sum if there are negative numbers (and thus can't be solved in polynomial time).

You can demand that the target value $C$ is nonzero, but this is insufficient---if $A$ is integral, then if $C = 1$ we can set $c = 1/2$ and again our algorithm is forced to obtain an exact answer.
In fact, $C$ must be more than polynomial to avoid a contradiction.
Thus, previous work has simply assumed a positive $A$, and we get a nice definition for what we want.

Note that if $A$ is positive, the interesting $C$ are very large, whereas with possibly-negative $A$ they may not be.  This is part of the reason that positive $A$ is a sufficient condition for interesting approximation algorithms.

On the other hand, positive $A$ is probably not quite necessary.  It is possible that one can limit $C$ and $A$ in such a way as to ensure that the problem is interesting even for possibly-negative $A$.  Looking at the reduction, it seems that $C >> NM$ may do the trick (if $M$ is the absolute value of the smallest negative number in $A$); particularly if $C$ is exponential in $N$, and $M$ is polynomial (in other words, the negative numbers of $A$ are all very small).  But at first glance, this seems to add complexity to the analysis without gaining much in return.  Also, more work would have to be done to make sure this matches the approximate subset sum definition correctly.

As for the reduction: that reduction as-is does not work well if the goal is $C = 0$.  Let's say, for example, that you start with a possibly-negative set $A = \{a_1,\ldots,a_N\}$, where the largest negative number is $\geq -M$, for a large positive $M$.  We want to find a subset that sums to 0.  Then, as per the reduction you cited, we construct $A' = \{a_1 + M,\ldots, a_N + M, M, \ldots, M\}$ with $N$ copies of $M$.  We want to find a subset that sums to $NM$.  This can trivially be accomplished by taking the $N$ copies of $M$.

Even if $C\neq 0$ this reduction doesn't work quite the way we would (probably) want.  We obtain a solution within $[(1-c)(NM + C),NM+C]$.  This may be significantly different than a solution within $[(1-c)C,C]$ for the original problem.  However, as noted above, if $C >> NM$ this is somewhat close to a $(1-c)$ approximation ratio.  We would need to be careful about solutions within $[C,NM+C]$, however.


Intersection of two arrays As part of a project i'm doing I have been looking for a way to find common values between 2 arrays including duplicates.
For example;
A = [2, 2, 3, 5]
B = [2, 2, 5]
would return the array;
Common values = [2, 2, 5]
I have attempted using sets, and the intersection function, but neither gave duplicates
Any help appreciated

Python-specific questions are probably off-topic here, but this question can be seen as a language-agnostic algorithmic task: given two arrays $A$ and $B$, each representing a multi-set, return an array containing the elements in the multiset $C = A \cap B$.
Here an element $x$ that has multiplicity $a$ in $A$ and $b$ in $B$, has multiplicity $\min\{a,b\}$ in $C$.
To solve this problem you can preliminary sort $A$ and $B$. Then, you can keep a pointer $p_A$ to some element of $A$ and a pointer $p_B$ to some element of $B$. Initially $p_A$ (resp. $p_B$) will point to the first element of  $A$ (resp. $B$).
I will use $A[p_A]$ (resp. $B[p_B]$) to denote the element of $A$ (resp. $B$) pointed by $p_A$ (resp. $p_B$). Also, it is convenient to assume that, whenever $p_A$ (resp. $p_B$) points past the end of $A$ (resp. $B$), $A[p_A]$ (resp. $B[p_B]$) has value $+\infty$.
Proceed similarly to the merge step of Mergesort:

Initialize $C$ as an empty array.
While ($p_A$ is not past the end of $A$) or ($p_B$ is not past the end of $B$)

If $A[p_A] = B[p_B]$:

Append $A[p_A]$ to $C$.
Advance $p_A$
Advance $p_B$.

Else if $A[p_A] > B[p_B]$:

Advance $p_B$

Else (in this case $A[p_A] < B[p_B]$):

Advance $p_A$


Find vertices of a convex polytope, defined by intersecting half-spaces I am looking for a algorithm that returns the vertices of a polytope if provided with the set of intersecting half-spaces  that define it.

In my special case the polytope is constructed by the following constraints on $x \in \mathbb{R}^d$:

$\sum_i x_i = 1$ (i.e., $\|x\|_1 = 1$).
$0 \le a_i \leq x_i\leq b_i \leq1$, where the $a_i,b_i$ are given

This can either be thought of as the intersection of the hyper-plane (defined by the first constraint, in combination with the range restriction of the second constraint) with a hyper-cube (defined by the second constraint) or as the intersection of half-spaces where the first constraint is the intersection of two half-spaces that only intersect on a hyper-plane.

This always generates a convex polytope, if I am not mistaken, as long as the intersection creates a bounded set.

I would like to have an algorithm that returns the set vertices of the polytope if provided with the set of $a_i$'s and $b_i$'s.

There is a special case where there exists no $x$ that satifies this condition. Ideally, this would be picked up on.
Therefore, I would wish for an algorithm that checks if such a polytope exists and if so returns the vertices.

Your problem is a special case of enumerating the vertices of a convex polytope, and there is an efficient (polynomial-delay) recursive algorithm for your special case, which I will describe next.

If $a_1+\dots+a_d > 1$, then there is no solution, and you can terminate.  If $a_1+\dots+a_d=1$, there is a single solution $(a_1,\dots,a_d)$, so output it and terminate.  Otherwise, I'll assume $a_1+\dots+a_d < 1$, so you use the following:

For each index $i$ such that $a_i<b_i$:

Let $c_i = 1-a_1-\dots-a_{i-1}-a_{i+1}-\dots-a_d$.
If $c_i \le b_i$, output $(a_1,\dots,a_{i-1},c_i,a_{i+1},\dots,a_d)$; it is a vertex of the original polytope.
Otherwise, replace $a_i \le x_i \le b_i$ with $b_i \le x_i \le b_i$ (i.e., replace $a_i$ with $b_i$) and recurse to output the vertices of the resulting polytope.

To help others find this by search: it's the intersection of the unit simplex (points of L1 norm exactly one) and an axis-aligned box.

In general, if the polytope is defined by an intersection $m$ half-spaces, then a vertex is defined by choosing a combination of $d$ out of the $n$ of the corresponding hyper-planes; if their intersection is a single point, and it is in the polytope, then it is a vertex.  This gives an exponential-time algorithm for enumerating all vertices for a general polytope.  There are other algorithms for the general case, but that's beyond the scope of this answer.


Matching two people. One has 7% in common with the other. The other has 70% in common. What's a fair match score? I am exploring some ideas around dating site matching, and I can do with some ideas as to which is the better solution

Senario: We have a boy and girl, the boy has completed his profile/bio thoroughly while the girl hasn't or maybe she just doesn't like a lot of things, so this is what the data looks like

Boy likes:                  Girl likes:
---------                   -----------
Painting                    Painting
Movies                      Movies
Long walks                  Long walks
Harry Potter                Harry Potter
Dogs                        Dogs
Pizza                       Pizza
Computer Science            Computer Science
Mercedes                    Ford
Traveling                   Daisies
Diving                      Psycology
...

Total things
---------------------------------------
100                         10

They share 7 things in common. To the girl the boy is a 70% match which is great
But to the boy the girl is only a 7% match

Maybe the girl would have more in common if she had more in her list of likes so maybe giving their match a 7/100 is a match missed and maybe that's all she likes and 7/100 is the best they'll ever match but even then, it still might be a good match because maybe the boy over filled his list of things he likes while the girl chose carefully what she really likes.

I am looking for ideas for an algorithm that would give the best match score to order them in lists with other people/matches who might have small percentage in matches because their lists of things they like are 1000s of entries long for example

Edit: I will not be matching strings, each of strings in the table above will have a unique ID in an RDBMS database. A table will be used to link users and topics

It seems you're looking for a symmetric set similarity measure.  (Symmetric since, as you point out, $A$ should match $B$ as much as $B$ matches $A$.  Set similarity since each person's preference is defined by a set of objects.)

A number of these are used in the CS literature.  Probably the most common is Jaccard similarity, defined by $|A\cap B|/|A\cup B|$.  In your example, $A$ and $B$ have 7 elements in common, and there are 103 elements between them, leading to a similarity of $7/103$.  A similar metric is Braun-Blanquet similarity, $|A\cap B|/\max\{|A|,|B|\}$; in your example this gives $7/100$.  With these as starting points you may be able to find further metrics that capture what you want better.  For example, here's a list I found while writing this.

What's notable about these metrics is that they don't take each person's dislikes into account---the similarity is defined only by what's on their list, not what's not on it.  (So you may think it makes a better match if two people don't like fish.)  Incorporating this would require a universe of elements (so any element in the universe not on the list is considered a dislike).  In this case you can use the classic Hamming Distance.  You have other options as well, like Euclidean distance or even the Sørensen-Dice similarity.

One benefit of using one of the above, well-known similarity measures is that you can use known algorithms to compute nearest neighbors quickly.


How does the MMU map multi-channel setups Given that the MMU does all the memory translations and etcetera, how does it maps a system consisted of multiple RAM chips?
Are their spaces concatenated (e.g Chip 1 + Chip 2)? If so, how does that works given ASLR?

ASLR has nothing to do with this. ASLR is a software technique to secure the applications where all executables are relocatable in that they keep information in the executable to relocate it to any address.
I would guess that the MMU doesn't see if there are several RAM DIMMs. It is the motherboard's job to make sure that if the memory controller of the CPU sets certain lines of the address bus, they are directed towards the right DIMM for decoding.
In hardware it could look like switches (transistors) activated by higher order bits of the address bus that will redirect all address lines to another DIMM. For example, if you have 2 DIMMs of 8GB each then the first DIMM needs 33 address lines for decoding because 2^33 bytes = 8GB. The second DIMM brings the computer to 16GB so, if you set any line of the address bus above 33, then the motherboard knows it needs to use the second DIMM.


Trying to find a substitution to solve a recurrence I'm trying to solve the  following recurrence.

\begin{align*}
B(2) &= 1\\
B(n) &= B(\lceil n  / \log_2 n\rceil)+\Theta(n)
\end{align*}

Here is my attempt:

\begin{align*}
B(n)
&= 3B(\lceil n/\log_2 n\rceil) + \Theta(n)\\
&= 3\big(3B(\lceil n/(\log_2 n)^2\rceil) + \Theta(n)\big) + \Theta(n)\\
&= 3\big(3\big(3B(\lceil n/(\log_2 n)^3\rceil)\big)\big) + 3^2\Theta(n) + 3\Theta(n) + \Theta(n)\\
&\ \ \vdots\\
&= 3^{k-1}B(\lceil n/(\log_2n)^{k-1}\rceil) + (1 + 3 + \dots + 3^{k-1})\Theta(n)\\
&= 3^{k-1} B(\lceil n/(\log_2 n)^{k-1}\rceil) + \frac{3^k-1}{3-1}\Theta(n)\,.
\end{align*}
Is there a substitution that I can use to make the term inside the function become 2?

Or any other smart method I can use to solve this problem?

I realised I made a mistake the expansion should be

\begin{align*}
B(n)
&= 3B(\lceil n/\log_2 n\rceil) + \Theta(n)\\
&= 3\big(3B(\lceil (n/(\log_2 n))/(\log_2(n/(\log_2 n) \rceil) + \Theta(n)\big) + \Theta(n)\\
&\ \ \vdots\\
\\
,.
\end{align*}

You don't need to try that hard. Instead, you can notice that on the one hand clearly $B(n) = \Omega(n)$, and on the other hand
$$
\begin{align*}
B(n) &= \Theta\left(n + \frac{n}{\log n} + \frac{n}{\log n \log(n/\log n)} + \cdots\right) \\ &=
O\left(n + \frac{n}{2} + \frac{n}{4} + \cdots\right) = O(n).
\end{align*}
$$
The first inequality holds since for $n$ larger than some constant, $\log_2 n \geq 2$ (you just need to stop the recursion once $n$ gets too small, at the cost of additional $O(1)$ which gets swallowed in the big Theta). The second inequality holds since $n+n/2+n/4+\cdots = 2n$.

Formally speaking, you can argue that $B(n) = B(n/2) + \Theta(n)$ grows faster than $B(n) = B(n/\log_2 n) + \Theta(n)$.


Algorithm books on a range of topics I've been tasked with building a library of books on algorithms for our small company (about 15 people). The budget is more than 5k, but certainly less than 10k, so I can buy a fair number of books. All people here have at least a Bachelor's degree in CS or a closely related field, so while I will get some basic textbook like Cormen, I'm more interested in good books on advanced topics. (I will get Knuth's 4 volumes, BTW.)

Some list of topics would be:

Sorting algorithms
Graph algorithms
String algorithms
Randomized algorithms
Distributed algorithms
Combinatorial algorithms
etc.

Essentially I'm looking for good recommendations on books about major topics within CS related to algorithms and data structures. Especially stuff that goes beyond what's typically covered in algorithm and data structure classes as part of a Bachelor's degree at a good school. I know the question is quite fuzzy, since I'm looking for generically useful material. The software we develop is mostly system level stuff handling large amounts of data.

The ideal would also be to find anything that would cover fairly recent cool data structures and algorithms, which most people might not have heard about.

EDIT: Here are some preliminary books that I think I should get:

Introduction to Algorithms by Cormen et al.
Algorithm Design by Kleinberg, Tardos
The Art of Computer Programming Vol 1-4 by Knuth
Approximation Algorithms by Vazirani
The Design of Approximation Algorithms by Williamson, Shmoys
Randomized Algorithms by Motwani, Raghavan
Introduction to the Theory of Computation by Sipser
Computational Complexity by Arora, Barak
Computers and Intractability by Garey and Johnson
Combinatorial Optimization by Schrijver

A few other books my colleagues wanted that deal with techniques and algorithms for language design, compilers and formal methods are:

Types and Programming Languages by Pierce
Principles of Model Checking by Baier, Katoen
Compilers: Principles, Techniques, and Tools by Aho, Lam, Sethi, Ullman
The Compiler Design Handbook: Optimizations and Machine Code Generation, Second Edition by Srikant, Shankar
The Garbage Collection Handbook: The Art of Automatic Memory Management by Jones, Hosking, Moss

I have not (nearly) read enough books to name $5000 worth of them. Therefore, I will suggest some groups of literature you should cover as well as point you towards selected representatives. I can not claim to have read most of the books in full myself, so I have to rely mostly on descriptions, cursory impression and reputation. I have looked into or worked with most of them to some extent, or had them recommended by experts.

I assume that you want your people to learn what can be done, and how to do it, as opposed to learning what they can't do. In particular, I will leave out books about computability and complexity theory as such; I expect your people to have taken away the relevant messages from their undergraduate education.

The Basics
Even though your people have learned them at some point, expect them to look
up the basics. Since sources like Wikipedia are frequently substandard
or outright wrong, you want to get them proper reference texts.

Popular choices include

Introduction to Algorithms by Cormen, Leiserson et al.
Very broad introduction that covers many elementary algorithms and data structures as well as basic analysis techniques. A standard text used frequently for teaching purposes and available in its 3rd edition (so most mistakes should have been purged by now). Lots of exercises.
Algorithms by Sedgewick and Wayne
Another standard text in its fourth edition. Less broad than Cormen, but with more attention to implementation details. Lots of material online, including a free course on Coursera. Lots of exercises.
Introduction to Algorithms -- A Creative Approach by Udi Manber
Also rather slim a selection of topics, but presented with attention to didactics. The focus is on inductive strategies. Contains lots of exercises and solutions (or at least hints) for some. A good secondary reference if you don't like the recommended textbook because of its unusual style.
Concrete Mathematics by Graham, Knuth and Patashnik
Covers discrete mathematics as relevant to algorithm analysis. Rare in its focus on computer science needs and rigor. Very high quality. Lots of exercises with solutions.

Analysis of Algorithms
In most standard text books, analysis of algorithm usually stops at the level
of $O$-asymptotics and RAM model. In order to estimate real-world efficiency
more reliably, it can be necessary to investigate runtime more precisely and
consider effects like memory hierarchy and communication.

An Introduction to the Analysis of Algorithms by Sedgewick and Flajolet
Basic techniques for precise analysis of algorithms. Written by the
pioneers of the field. Also has a free online course.
The Art of Computer Programming by Knuth
The reference for high-quality, low-level, precisely analysed
algorithms for a whole range of problems. Also serves as reference.

Advanced Surveys

Purely functional data structures by Okasaki
Classic and basic literature often focuses on the procedural paradigm. If
you want to work in the functional paradigm, new techniques for efficient
data structures are needed. This book is a detailed overview over the area.
Advanced Data Structures by Brass
Sometimes, the basic techniques are not enough. This is an overview over
advanced data structures, with code and many references.
Algorithmics for Hard Problems by Hromkovič
Complexity theory tells us (as practitioners) not to bother looking for
exact yet efficient algorithms for many natural problems. There are plenty
of techniques for practically solving these problems; this text shows
you how.

Specialised Literature

Compilers: Principles, Techniques, and Tools aka The Dragon Book by Aho et al
Should you ever need to build or tinker with a compiler, this is the
standard text on the area.
Network Flows: Theory, Algorithms, and Applications by Ahuja
Many problems can be modeled as network  flow problems; this book gives you
a full coverage of the field.
Probabilistic Graphical Models by Koller and Friedman
Graphical models are a major tool in modeling scenarios for machine
learning (among others) probabilistically. This is a comprehensive overview
about the complex. There is a related free online course.
Handbook of Exact String Matching Algorithms by Charras and Lecrog
String matching is an ever important task when dealing with data.
This book lists most (if not all) relevant algorithms for the job,
including high-level descriptions as well as implementations.
Analytic Combinatorics by Sedgewick
and Flajolet
The deep mathematical dive after "An Introduction to the Analysis of
Algorithms" by the same authors. Not for everybody, but gold for the
interested.
Algorithms on Strings, Trees and Sequences by Gusfield
Should you ever have to deal with huge amounts of string data (in
particular in biology contexts) this is the go-to book as it provides an
overview over the relevant data structures and algorithms.

For the Practitioner

Patterns for Parallel Programming by Mattson et al.
In practice, you might want to utilise multiple machines to deal with
large problems. This book is a high-level, example-driven overview
over ways to do so, that is how to organise and move data and computing
agents. It also addresses ways to implement them with existing tools.
A Guide to Experimental Algorithmics by McGeoch
When theoretical analysis is too hard or too coarse, you have to perform
experiments. This is an introduction into how to properly design
experiments on algorithms.
The Definitive ANTLR 4 Reference by Parr
You often need domain specific languages and tools to parse them. ANTLR is
a mature and convenient compiler generator, and this is the book best
suited for learning how to use it. Parr also has some other books on
DSLs worth checking out.

If you want very recent material, you should consider getting your people access to journals and conference proceedings, maybe by cooperating with a university library. You can also actually let them attend conferences on topics relevant to them resp. your company.

Also, consider asking your people. Have them do their own research (including free samples or copies on the web or libraries) and they will tell you which books they consider relevant to their work. There is no use in buying stuff no one will read.


Non-deterministic TM and problems in class P Definition:
$P$ is the set of languages that can be decided by a deterministic Turing Machine in polynomial time.

I wonder if:
$P$ equals to the set of languages that can be decided by a non-deterministic Turing Machine in polynomial time?

I think this also has to be true in this case because a non-deterministic Turing Machine can also decide all problems which can be decided by a deterministic Turing Machine. Because of the fact that we have here a language in P this NTM also decides it in P.

Am I right or am I wrong?

The class $P$ is a subset of $NP$. For an $NP$ algorithm to simulate $P$ in polynomial time, it does not even need to use nondeterminism, since a single branch can solve the $P$ problem.

It could be a bit confusing though when textbooks say that an $NP$ algorithm works in 'polynomial time'. But this refers to the amount of time it takes for a single branch to compute. But taken as a whole, $NP= \cup NTIME(n^k)$, while $P= \cup DTIME(n^k)$.


Lower bound the difference between distinct values of a function over a discrete domain? I have a function $f: X \to \mathbb{R}$ where the domain $X$ is a (small) discrete set, such as $X = \mathbb{Z}^d \cap [-10,10]^d$ (i.e., the set of $d$-dimensional integer vectors all of whose coordinates are in the range $-10..10$, inclusive).

I'm interested in computing a non-trivial lower bound on the value of

$$\min_{\substack{x_1 \neq x_2 \\ x_1,x_2 \in X}} \big|~f(x_1) - f(x_2)~\big|$$

One possible approach is exhaustive search. Say there are $N = |X|$ distinct elements in the domain. Then I would compute $f(x)$ for each $x \in X$, and then calculate the difference between the $f(x_1)-f(x_2)$ for each pair of distinct values $(x_1,x_2) \in X$. This would require $N$ evaluations of $f$ and $N(N-1)$ operations between the values.

My questions are:

Has someone has seen this type of problem before. I'd like to find out more about related problems, but I just don't know what are the right terms to look for in the literature.
Is it possible to do better by exploiting properties of $f$? I'm looking to compute the "minimum difference in function values" for a functions such as $\log(1+\exp(-s^Tx))$ (i.e., convex, continuous, monotonically decreasing in $s^Tx$ where $s \in \mathbb{R}^d$; this is the logistic loss function that is optimized in machine learning applications).

You can certainly do better than $N(N-1)$: you can achieve $O(N \lg N)$ running time.  Evaluate $f$ on every possible element of $x$, then sort the resulting values, and look at the gap between consecutive values.  The smallest such gap is exactly the value of $\min |f(x_1)-f(x_2)|$.

As Raphael says, without any information about $f$, it seems unlikely that you can do any better than to evaluate $f$ on every possible input.  Indeed, it seems possible to prove this using an adversarial argument, in a black-box setting: if there is a single value $x^*$ where you haven't evaluated $f(x^*)$, then any answer your algorithm outputs can be made to be wrong by choosing the value of $f(x^*)$ appropriately.

Since the notion of "monotonically non-decreasing" is not defined when the domain is not totally ordered (as in your example for $X$), and the notion of continuous is not defined when the domain is discrete (i.e., not continuous, as in your example for $X$), your second question isn't well-formed and can't be answered in its current state.


Finite Automata: Final vs Accepting States What is the difference between a final and accepting state when addressing an automaton?

As I understand it, a final state is depicted (traditionally) with a double circle, and apparently so is an accepting state. So if they are both depicted with the same symbol, what makes  a state particularly accepting?

Those are two words that mean exactly the same thing.


Algorithm Question: Stacking bricks of different colours? I have a bunch of coloured bricks. There are X different colours, and a random number of each colour. How do I stack them up into Y columns so that a) no row has two bricks of the same colour and b) the height of the largest column is minimised?

There is an obvious lower bound of highest number of bricks of a single colour but beyond that I don't know where to go. This is equivalent to an optimisation problem I'm trying to solve and I'd be grateful if someone recognised the problem!

Let $n$ be the number of bricks and $c_i$ be the number of bricks of color $i$.
First notice that in a $w \times h$ grid we can fit at most $wh$ bricks.
Therefore, $\lceil \frac{n}{Y} \rceil$ is a lower bound on your height. The
minimum height $h$ to stack all your bricks without violating the constraint will be
$\max(\max_i(c_i), \lceil \frac{n}{Y} \rceil)$.

The idea is to go from left to right (column 1 to X) and keep pushing a brick of the same color on to the left most non-full stack. And by non-full I mean that the size of the stack is lower than our defined height $h$. No two colors will be in the same row and it is also obviously true, that we have enough room for all $n$ bricks.

A pseudo code is also provided:

color_count[i] = number of bricks of color i
height = max(max(color_count), ceil(n / Y))

current_column = 1
current_row = 1
current_color = 1
while current_color <= X
  while color_count[current_color] > 0
    put a brick at (current_row, current_column) with current_color
    color_count[current_color] -= 1
    if current_row == height
      current_column += 1
      current_row = 1
    else
      current_row += 1
  current_color += 1


Measures and probability in formal language theory I am looking for references for the following problem:
I have a very special class of regular languages and my aim is to express (and to justify my conjecture) that this class itself is very small in some way (as a subset of the regular languages) and that the languages contained in this class are rather "bloated".

For the latter point, I could prove that all languages in the class have a large diameter with respect to many common metrics on strings. However, I want to consider the following: Given a language from the class, we know it has a large diameter, but does it also have a large "volume" (that is, measure), or put differently, if I choose randomly a finite word, is there anything meaningful to say about how "probable" it is that the word belongs to the language? Of course, we can lift the problem: Picking a random language, how probable is it to get a language in the class?

Are there any references or standard approaches for looking at classes of (regular) languages from this point of view (or is this considered as generally uninteresting)?

There is the concept of density of languages (see e.g. here). The density $\operatorname{den}_L : \mathbb{N} \to [0,1]$ of $L \subseteq \Sigma^*$ is defined by

$\qquad \operatorname{den}_L(n) = \frac{|L \cap \Sigma^n|}{|\Sigma^n|}$.

For any fixed length, the density corresponds to the probability of picking a word from the language, assuming we pick uniformly at random. Add a distribution over lengths and you may have what you need.

You may be able to express your concept of "volume" in terms of this notion, maybe by investigating $\lim_{n \to \infty} \operatorname{den}_L(n)$.

As for "randomly picking a language" -- how would you do that? There are uncountably many languages over any given alphabet so I'm not sure how you would define a (nice) probability distribution.


When to add and when to multiply to find time complexity I am trying to learn how to determine time complexity. Sometimes, I see complexity as $\log n + \log n = 2\log n$ but sometimes I see complexity as $\log n\cdot\log n$ which is $(\log n)^2$.

Suppose I need to do two binary searches to find two different elements, in one algorithm. Is this $\log n + \log n$ time, or would it be $(\log n)^2$ time?

You add time complexities when you have something of the form: do operation $A$, then do operation $B$. This would be (time complexity of $A$) + (time complexity of $B$).

You multiply time complexities when you have something of the form: do operation $A$, $X$ times (eg. in a for loop). This would be $X \cdot $(time complexity of $A$).

If you perform two binary searches, each of which has time complexity $\log n$, the total runtime is $\log n + \log n$. You might see a runtime of $(\log n)^2$ if you had to perform $\log n$ binary searches.


A non-regular language satisfying the pumping lemma I got a problem to solve, which is to demostrate that the language $L$, given by:

$L = \{ab^nc^n\mid n \geq 0\} \cup \{a^kw \mid k\geq 2 \wedge w \in \Sigma^*\}$

Satisfies the pumping lemma.
Is not regular.

For the question 1. I think it would suffice to demonstrate that for all $w \in L$, $w$ can be decomposed in the form $\alpha \beta \gamma$, where $|\beta| \neq 0$, and that every string $\alpha \beta^m \gamma \in L$, where $m \geq 0$, but after that I have no clear what I have to do, because I start thinking about cases, what if I have a string $w \in \{ab^nc^n\mid n \geq 0\}$... I should decompose it the way $\alpha = \epsilon, \beta = a$ and $\gamma = \text{the rest of the string}$ (because if we use $w = ab^0c^0 = a$, $\beta$ will have to be $a$, because we know that $\beta \neq \epsilon$), but in this case $\alpha \beta^m$ may not be in $L$, for example, if we choose $m = 0, \alpha \beta^m \gamma$ won't be in $L$, so I don't know what I'm doing wrong... perhaps I'm making mistakes in several steps.

Now, for the question 2. I don't even have an idea on how to start, if someone would help me I would really appreciate it

You are not supplying the definition of $L$, so here is one definition which works:

$$ L = \{ a b^n c^n : n \geq 0 \} \cup \{ a^k w : k \neq 1 \text{ and } w \in \Sigma^* \text{ doesn't start with $a$} \}. $$

Choose a pumping length of $2$. A word $ab^nc^n \in L$ can be pumped by pumping the $a$ part. A word $aaw$ can be pumped by pumping the $aa$ part. Finally, a word $bw$ or $cw$ can be pumped by pumping the $b$ part or $c$ part.

Your definition seems to be

$$ L' = \{ a b^n c^n : n \geq 0 \} \cup \{ a^k w : k \neq 2 \text{ and } w \in \Sigma^* \}, $$

but for this language the pumping lemma does work. Indeed, apply it to $ab^nc^n \in L'$ for large enough $n$. Then $ab^nc^n = xyz$ so that $|y| \geq 1$ and $xy^iz \in L'$ for all $i \geq 0$. Considering the case $i = 2$, we see that $y = a$ necessarily. But then, taking $i = 0$ we get $xz = b^nc^n \notin L'$.

Perhaps the exercise meant you to use the version of the pumping lemma in which $i \geq 1$ instead of $i \geq 0$.

We can show that $L$ is not regular in many ways:

Use one of the many general versions of the pumping lemma which can force the $b^nc^n$ to be pumped. For example, the general version on Wikipedia states that there exists $p$ such that any word $uwv \in L$ with $|w| \geq p$ can be partitioned as $w = xyz$ so that $|xy| \leq p$, $|y| \geq 1$ and $uxy^iz \in L$ for all $i \geq 0$. Choose $u = a$, $w = b^nc^n$ for $n \geq p$ and $v = \epsilon$, and follow the usual argument.
If $L$ were regular then $L \cap ab\Sigma^* = \{ ab^nc^n : n \geq 1 \}$ would also be regular, and you can prove that it isn't using the usual pumping lemma.
Use the Myhill–Nerode criterion. The words $ab^n$ are pairwise inequivalent, and so $L$ is not regular.


Computable Functions I'm learning about computable functions. Our definition for computable function is as follows:

Informally, a computable function is a function f : A → B such
that there is a mechanical procedure for computing the result
f(a) ∈ B for every a ∈ A.

they go on to give the following non-example:

A function that takes an input p (which I assume to be a program), and checks if p is a syntactically valid Python program without any user interaction that terminates and returns 1 if this is true, 0 otherwise.

I was just trying to understand why this is not computable. I know when I write a program with incorrect syntax that I get an error when I try to run it, so I am assuming that it is possible to check whether a program is syntactically correct, but I have a hunch that the terminating part has to do with the halting problem. Is this simply just an obscured halting problem?

Yes, "that terminates" is the halting problem, not really in disguise but also not pointed out as problematic.


How to prove the outcome of both segment of code are equal Is it possible to prove using induction? If possible what would be the steps to proof A=B?

Main thing i want to proof is outcome of two segments of code are same.

Below is the code:

Segment A:

int A (int x, int y) {
  if (y==0) return x;
  return A(y, x % y);
}

Segment B:

int B (int x, int y) {
   while (y!=0) {
      int t = y;
      y = x % y;
      x = t;
   }
   return x;
}

Proof idea: first of all note that the version A is a recursive version of B.
Both A and B halts when $y$ is 0, so in both cases computation lasts until $y$ reaches zero. In both versions the return value is $x$. Also note that each recursive call corresponds to a single step in the while loop. So you can prove that after each recursive call and after each step of the while-loop values of $x$ and $y$ are equals. Induction on the number of steps where we assume $x, y > 0$.

Base step: step 1. In the recursive call (version A) $y$ value is passed as an argument and assigned to $x$ (stored in $x$), but new $y$ takes $x\%y$. In other words, ($x_{new} \leftarrow y_{prev}$ and $y_{new} \leftarrow x_{prev} \% y_{prev}$). Similarly, in the version B the following assignments

int t = y;
y = x % y;
x = t;

implies that $x_{new} \leftarrow y_{prev}$ and $y_{new} \leftarrow x_{prev} \% y_{prev}$. So after the first step in both segments  new $x$ and new $y$ values are equal.

Induction: assume that after $n$ steps of recursive call and while-loop $x$ and $y$ values are equal. Then by the same argument as in the Base step for step $n+1$ $x_{new}$ and $y_{new}$ in both codes are equal. Thus, when we $y = 0$ both segments return $x$s which are equal.

Alternatively, you could separately prove that both functions compute gcd of two integers $x$ and $y$ and deduce that they must give the same output for same inputs $x$ and $y$. You can do it yourself. Please look here.


Master Theorem: How to find the value of b in this recurrence relation The master theorem is used with recurrences of the form T(n) = aT(n/b) + f(n) where a >=1 and b > 1, in which case the value of b can be easily seen from the recurrence, however I have a recurrence of the form

T(n) = T((n/4)+3) + f(n)

How do I get the value of b in this case?

This question Particularly Tricky Recurrence Relation (Master's Theorem) is the only thing I found that has a similar case with T(n/4 +1) but gives no detail about how the b was calculated.

You can't use the Master theorem on that function $T$.

However, as Raphael suggests, you could consider the related function

$$T'(n) = T'(n/4) + f(n),$$

use the Master theorem to find a solution for $T'$, and then check whether that's a valid solution for $T$ too.  No guarantees that it will be, but you could check.

In other words, you could use the guess-and-check strategy to solve the recurrence for $T$, where your "guess" comes from solving $T'$ using the Master theorem.  See also Solving or approximating recurrence relations for sequences of numbers for an explanation of guess-and-check (also called guess-and-prove).

One caveat is that guess-and-check will probably require an explicit solution to $T$, with specific constants.  In other words, it's usually not enough to guess that $T(n) = O(g(n))$; you will typically need to guess a specific constant $c$ such that $T(n) \le c \cdot  g(n)$, one that will enable the proof to go through.


Arbitrary Turing machine run time analysis on the empty word Consider $L = \{ \langle M,n \rangle : M $ accpets $\epsilon $ in less than $T(n)$ steps$\}$

This language is decidable because a decider can simulate $M$ on $\epsilon$ and accept if it accepts and reject if it rejects or passed more than $T(n)$ steps.

The decider above will run in $O(T(n)log(T(n)))$ time corresponding to simulation time bounds (maybe even $O(T(n))$ has been achieved for simulation time of $T(n)$ steps)

but since we are dealing with a constant word, might it have a better simulation time? $o(T(n))$?

The $\log T(n)$ factor in the analysis stems from the need to keep (and update) a step counter, in binary, that goes up to $T(n)$. This requires $\log(T(n))$ cells, and the need to update it (or rather, to drag it along on the tape) costs $\log(T(n))$ in every iteration.

Now, if you could avoid this for $\epsilon$, then you could avoid it for an arbitrary input word $w$, by modifying the given TM $M$ to a new TM $M'$ that first writes $w$ on the tape, and then simulates $M'$ for $T(n)+|w|$ steps on $\epsilon$.

Since $T(n)$ is super-linear, this would contradict the best known lower bounds.

Note that this does not prove that a better simulation is not possible, only that the word $\epsilon$ plays no special role.

In fact, however, you could prove that $o(T(n))$ is not achievable, by tweaking slightly the Time Hierarchy Theorem


Length of distinguishing string for a DFA Is it possible for a $DFA$ which has $n$ states that, there exists two distinguishable states $p, q$ such that there exists a distinquishing string between $p$ and $q$ whose length is greater than $n$?

Distinguishing strings can, in general principle, be of any length, though the specifics will depend on the automaton and states that you're looking at.

For example, consider the usual automaton that accepts even-length strings over the alphabet $\{1\}$. We have states $q_\mathrm{e}$ (which is the start state and is accepting) and $q_\mathrm{o}$ (which is not accepting), and the transition function just swaps state every time a character is read.  For this automaton, every string over $\{1\}^*$, including the empty string, distinguishes the two states. Strings of even length (including $\epsilon$) distinguish because they're accepted by $q_\mathrm{e}$ and rejected by $q_\mathrm{o}$; odd-length strings are the other way around.


Static scope and dynamic scope I am perpetually confused when it comes to static scoping and dynamic scoping and their differences and Wikipedia isn't of any help, so here's my question:

Given the following pseudo code in a hypothetical programming environment, what are the outputs under the following conditions?

call by need using static scope
call by name using dynamic scope

global int n = 100, m = 5;
void fun(x){
    int n = 10;
    print(x + 10);
    n = 200;
    m = 20;
    print(x);
}
main(){
    fun(n + m);
}

Additionally, what would be two environments where I can run this code to check the output with the conditions? C uses lexical scope, but it does not support call by need while Bash supports dynamic scope, I guess!

Here is the simulation by hand.

call by need using static scope

The function receives as x parameter the thunk [n+m] bound to the
globals. Then local n gets 10. The print statement requires evaluation
of the thunk, which becomes 100+5, i.e. 105. It prints 105+10,
i.e. 115. Local n and global m are changed, but this cannot affect x for two
reasons: the thunk does not depend on the local variable n (because
statically bound to the global variables n and m), and it is already evaluated to 105
anyway, which is printed by the second  print.

Note that, if the first print statement were removed, then x would be evaluated after changing the global variable m, which would then be 20 instead of 5, and the answer for the remaining print statement (formerly the second one) would be 120.

result: 115 105
call by name using dynamic scope

The function receives as x parameter the unbound expression [n+m]. Then
local n gets 10. Then x gets evaluated, with local n=10  and global m=5,
i.e. 15, and added 10 to print 25. Then local n=200 and global m=20. The
parameter x is reevaluated as 200+20, i.e. 220, which gets printed.

result: 25 220

How to test it? One would have to check various implementations of
programming languages. I do not remember off hand.

Call by need is usually found in functional languages, which normally
do not have assignment. But some still allow it. So I would look for
that regarding the first case. I think CAML may provide it.

Call by name is fairly rare, and rather weird in a dynamic scope
context. I do not know of any language that will offer that
combination. The best is to use a dynamic binding langage and simulate
the example by explicitly replacing the call by name argument by a
parameterless function that has the parameter as body.

In the example, you would call in main(): fun(lambda().n+m), and
in the body of the function fun you would replace x by the call x().


Predicate Logic Notation: What does a "dot" mean? What does a dot (.) mean in predicates?

$\forall a \in A. \exists d \in D. H(a,d)$

Especially, how is the above different to

$ \exists d \in D. \forall a \in A. H(a,d)$

I've never seen this used in German lecture scripts.

The dot just means "such that"; it's often omitted.

The difference between the two formulas is the difference between "everybody has a mother" and "there is somebody who is everybody's mother."


NL and NP compute different binary relations, so what? Let the binary relation computed by a nondeterministic transducer be the relation between input strings and the possible output strings the transducer can produce (and accept) for the given input string.

It is easy to see that the nondeterministic transducers using polynomial time can compute different binary relations than the nondeterministic transducers using logarithmic space. (Trivial examples like $\{(1^n,ww^R):n\in\mathbb N, |w|\leq n\}$ suffice to see this. Edit: This assumes that the output is generated symbol by symbol, see András Salamon's comment. If random access to write only output memory is assumed, then $\{(1^n,w):n\in\mathbb N, w\in D_2, |w|\leq 2n\}$ where $D_2$ is the Dyck language of all strings of matching brackets over two pairs of brackets, say $\{ [,], (,) \}$ is an example. However, proving that this example really works is non-trivial.)

Can anything of interest be concluded from this basic observation? For example, concluding that there must exist an oracle $A$ such that $NL^A \neq NP^A$ would be of interest, but things don't work that way. Or concluding that directly programming in NP is easier that directly programming in NL, because more powerful subroutines are available. That sort of sounds true, even so subroutines generally can have more that a single input string and produce more than a single output string. (So one could try to prove that if all those possible subroutines would be equal, then there could not exist an oracle for which the relativized decision problems are different. But even this will probably fail.)

Edit:

WLOG, we can restrict us to NL tranducers that never repeat a configuration. These are exactly those NL transducers that only use polynomial time.
The random access to write only output memory is well outside NL. But it is still inside NP, so the composition of those NL transducers could be done inside NP. This should be good enough to conclude things about powerful subroutines or oracles, if this is possible at all. (Even the symbol by symbol output tape was outside of NL, it was just less obvious.)
The oracles $A$ such that $NL^A \neq NP^A$ are white box oracles, where the problem $A$ is (expected to be) outside of the considered complexity classes. The conclusions about subroutines from the basic observation might tell us something about black box oracles from the same or weaker complexity classes. Or they might at least provide a motivation to prove black box separations between complexity classes relative to oracles from weaker complexity classes.

We know that $NL \subseteq NP$, but that $NL \subsetneq NP$ is not known. So one cannot outright say that $NL$ and $NP$ are different.

We only know for sure $NL \subsetneq PSPACE \subsetneq EXPSPACE$ by space hierarchy theorem. And $P \subsetneq EXPTIME$,and $NP \subseteq NEXPTIME$ by time hierarchy theorem.

We only know for sure is
$$L\subseteq NL \subseteq P \subseteq NP \subseteq PH \subseteq PSPACE =NPSAPCE \subseteq EXPTIME \subseteq NEXPTIME\subseteq EXPSPACE$$

Only above four inclusions are known to be strict. All the other inclusions are unknown and open problems. (Though most but not all have unproven belief that each of them is strict).

See https://en.wikipedia.org/wiki/PSPACE#Relation_among_other_classes.

Also, I think, we might be able to prove that there exists a language $B$ for which $NL^B \neq NP^B$. Probably $U_B$ and $B$ of Baker, Gill and Soloway will work here too. And we are also able to show that $NL^A = NP^A$ for $A = TQBF$, the $PSPACE$ complete problem to decide the true quantified Boolean formulas.


Computing the hit and miss ratio of a cache organized as either direct mapped or two-way associative This is an example problem in a computer organization and architecture course that's giving me some trouble. It goes as follows:

  Consider a cache of 4 lines of 16 bytes each. Main memory is divided
  into blocks of 16 bytes each. That is, block 0 has bytes with
  addresses 0 through 15, and so on. Now consider a program that
  accesses memory in the following sequence of addresses:

  Once: 63-70

  Loop 10 times: 15-32; 80-95

  a. Suppose the cache is organized as direct mapped. Memory blocks 0,
  4, and so on are assigned to line 1; blocks 1, 5, and so on to line 2;
  and so on. Compute the hit ratio.

  b. Suppose the cache is organized as two-way set associative, with two
  sets of two lines each. Even-numbered blocks are assigned to set 0 and
  odd-numbered blocks are assigned to set 1. Compute the hit ratio using
  the least recently used replacement scheme.

I know that the formula for finding the hit ratio is:

hit ratio = hits / (hits + misses)

and that the LRU replacement scheme should be used for both a and b, since it's the most efficient. I know how to find and compute addresses in a cache, but this has me stumped.

Any help in understanding this is greatly appreciated!

Consider a cache of 4 lines of 16 bytes each. Main memory is divided
  into blocks of 16 bytes each. That is, block 0 has bytes with
  addresses 0 through 15, and so on.

Number of cache lines = 4

Each cache line = 16 bytes

Main memory block size = 16 bytes

Block 0 holds address 0 to 15,Block 1 holds address 16 to 31,Block 2 holds address 32 to 47, etc as below

╔══════════════════════════╗
║       Main Memory        ║
╠════════════════╤═════════╣
║ Memory address │         ║
╟────────────────┼─────────╢
║       0        │ Block 0 ║
╟────────────────┤         ║
║       1        │         ║
╟────────────────┤         ║
║       2        │         ║
╟────────────────┤         ║
║       3        │         ║
╟────────────────┤         ║
║       4        │         ║
╟────────────────┤         ║
║       5        │         ║
╟────────────────┤         ║
║       6        │         ║
╟────────────────┤         ║
║       7        │         ║
╟────────────────┤         ║
║       8        │         ║
╟────────────────┤         ║
║       9        │         ║
╟────────────────┤         ║
║       10       │         ║
╟────────────────┤         ║
║       11       │         ║
╟────────────────┤         ║
║       12       │         ║
╟────────────────┤         ║
║       13       │         ║
╟────────────────┤         ║
║       14       │         ║
╟────────────────┤         ║
║       15       │         ║
╟────────────────┼─────────╢
║       16       │ Block 1 ║
╟────────────────┤         ║
║       17       │         ║
╟────────────────┤         ║
║       18       │         ║
╟────────────────┤         ║
║   and so on    │         ║
╚════════════════╧═════════╝

  Now consider a program that accesses memory in the following sequence
  of addresses:

  Once: 63-70

  Loop 10 times: 15-32; 80-95

Here its not correctly specified that-

Case 1 : looped 15-32 ten times and then looped 80-95 ten times

Case 2 : 15-32 and 80-95 are looped one after another ten times

anyway we'll solve both cases.

  a. Suppose the cache is organized as direct mapped. Memory blocks 0,
  4, and so on are assigned to line 1; blocks 1, 5, and so on to line 2;
  and so on. Compute the hit ratio.

Direct mapped Cache :

╔═════════════╤═══════════════════╤═════════════════════════╗
║ Cache lines │ Main memory block │ Addresses in each block ║
╠═════════════╪═══════════════════╪═════════════════════════╣
║      0      │      Block 0      │          0-15           ║
╟─────────────┼───────────────────┼─────────────────────────╢
║      1      │      Block 1      │          16-31          ║
╟─────────────┼───────────────────┼─────────────────────────╢
║      2      │      Block 2      │          32-47          ║
╟─────────────┼───────────────────┼─────────────────────────╢
║      3      │      Block 3      │          48-63          ║
╟─────────────┼───────────────────┼─────────────────────────╢
║      0      │      Block 4      │          64-79          ║
╟─────────────┼───────────────────┼─────────────────────────╢
║      1      │      Block 5      │          80-95          ║
╟─────────────┼───────────────────┼─────────────────────────╢
║      2      │      Block 6      │         96-111          ║
╚═════════════╧═══════════════════╧═════════════════════════╝

Accessing memory:

(1) once: 63-70

63 falls in Block 3 - Miss on 63 (Block 3 is bought to cache)

64 falls in Block 4 - Miss on 64 (Block 4 is bought to cache)

╔═════════════╤═══════════════════╤═════════╗
║ Cache lines │ Main memory Block │ Address ║
╠═════════════╪═══════════════════╪═════════╣
║      0      │      Block 4      │  64-79  ║
╟─────────────┼───────────────────┼─────────╢
║      1      │         -         │    -    ║
╟─────────────┼───────────────────┼─────────╢
║      2      │         -         │    -    ║
╟─────────────┼───────────────────┼─────────╢
║      3      │      Block 3      │  48-63  ║
╚═════════════╧═══════════════════╧═════════╝

therefore, 2 miss and 6 hit.

(2) loop: 15-32,80-95

Case 1:

15 falls in Block 0 - Miss on 15 (Block 0 is bought to cache, replacing Block 4)

16 falls in Block 1 - Miss on 16 (Block 1 is bought to cache)

32 falls in Block 2 - Miss on 32 (Block 2 is bought to cache)

╔═════════════╤═══════════════════╤═════════╗
║ Cache lines │ Main memory Block │ Address ║
╠═════════════╪═══════════════════╪═════════╣
║      0      │      Block 0      │  0-15   ║
╟─────────────┼───────────────────┼─────────╢
║      1      │      Block 1      │  16-31  ║
╟─────────────┼───────────────────┼─────────╢
║      2      │      Block 2      │  32-47  ║
╟─────────────┼───────────────────┼─────────╢
║      3      │      Block 3      │  48-63  ║
╚═════════════╧═══════════════════╧═════════╝

80 falls in Block 5 - Miss on 80 (Block 5 is bought to cache, replacing Block 1)

╔═════════════╤═══════════════════╤═════════╗
║ Cache lines │ Main memory Block │ Address ║
╠═════════════╪═══════════════════╪═════════╣
║      0      │      Block 0      │  0-15   ║
╟─────────────┼───────────────────┼─────────╢
║      1      │      Block 5      │  80-95  ║
╟─────────────┼───────────────────┼─────────╢
║      2      │      Block 2      │  32-47  ║
╟─────────────┼───────────────────┼─────────╢
║      3      │      Block 3      │  48-63  ║
╚═════════════╧═══════════════════╧═════════╝

therefore, 4 miss and 29 hit.

Case 2 : loop: 15-32,80-95

{{ 15 falls in Block 0 - Miss on 15 (Block 0 is bought to cache, replacing Block 4)

16 falls in Block 1 - Miss on 16 (Block 1 is bought to cache)

32 falls in Block 2 - Miss on 32 (Block 2 is bought to cache)

80 falls in Block 5 - Miss on 80 (Block 5 is bought to cache, replacing Block 1) }} x 1 times

{{ 16 falls in Block 1 - Miss on 16 (Block 1 is bought to cache, replacing Block 5)

80 falls in Block 5 - Miss on 80 (Block 5 is bought to cache, replacing Block 1) }} x 9 times

therefore, 22 miss and 11 hit.

  b. Suppose the cache is organized as two-way set associative, with two
  sets of two lines each. Even-numbered blocks are assigned to set 0 and
  odd-numbered blocks are assigned to set 1. Compute the hit ratio using
  the least recently used replacement scheme.

Two-way set associative mapping:

╔═════════════════════════════╗
║            Cache            ║
╠═════════════╤═══════╤═══════╣
║ Cache lines │ Set 1 │ Set 2 ║
╟─────────────┼───────┼───────╢
║      0      │   -   │   -   ║
╟─────────────┼───────┼───────╢
║      1      │   -   │   -   ║
╚═════════════╧═══════╧═══════╝

Block allocation to cache lines:

╔═════════════╤═══════════════════╗
║ Cache lines │ Main memory Block ║
╠═════════════╪═══════════════════╣
║      0      │  Block 0,2,4,..   ║
╟─────────────┼───────────────────╢
║      1      │  Block 1,3,5,..   ║
╚═════════════╧═══════════════════╝

Accessing memory:

(1) once: 63-70

63 falls in Block 3 - Miss on 63 (Block 3 is bought to cache)

64 falls in Block 4 - Miss on 64 (Block 4 is bought to cache)

╔═══════════════════════════════╗
║             Cache             ║
╠═════════════╤═════════╤═══════╣
║ Cache lines │  Set 1  │ Set 2 ║
╟─────────────┼─────────┼───────╢
║      0      │ Block 4 │   -   ║
╟─────────────┼─────────┼───────╢
║      1      │ Block 3 │   -   ║
╚═════════════╧═════════╧═══════╝

therefore, 2 miss and 6 hit.

(2) loop: 15-32,80-95

Case 1:

15 falls in Block 0 - Miss on 15 (Block 0 is bought to cache)

16 falls in Block 1 - Miss on 16 (Block 1 is bought to cache)

32 falls in Block 2 - Miss on 32 (Block 2 is bought to cache, replacing Block 4)

╔═════════════════════════════════╗
║              Cache              ║
╠═════════════╤═════════╤═════════╣
║ Cache lines │  Set 1  │  Set 2  ║
╟─────────────┼─────────┼─────────╢
║      0      │ Block 2 │ Block 0 ║
╟─────────────┼─────────┼─────────╢
║      1      │ Block 3 │ Block 1 ║
╚═════════════╧═════════╧═════════╝

80 falls in Block 5 - Miss on 80 (Block 5 is bought to cache, replacing Block 3)

╔═════════════════════════════════╗
║              Cache              ║
╠═════════════╤═════════╤═════════╣
║ Cache lines │  Set 1  │  Set 2  ║
╟─────────────┼─────────┼─────────╢
║      0      │ Block 2 │ Block 0 ║
╟─────────────┼─────────┼─────────╢
║      1      │ Block 5 │ Block 1 ║
╚═════════════╧═════════╧═════════╝

therefore, 4 miss and 29 hit.

Case 2 : loop: 15-32,80-95

15 falls in Block 0 - Miss on 15 (Block 0 is bought to cache)

16 falls in Block 1 - Miss on 16 (Block 1 is bought to cache)

32 falls in Block 2 - Miss on 32 (Block 2 is bought to cache,, replacing Block 2)

80 falls in Block 5 - Miss on 80 (Block 5 is bought to cache, replacing Block 5)

therefore, 4 miss and 29 hit.

Answer:

a.

Case 1: hit ratio = (6+29)/(8+18+15) * 100 = 85.3%

Case 2: hit ratio = (6+11)/(8+18+15) * 100 = 41.1%

b.

Case 1: hit ratio = (6+29)/(8+18+15) * 100 = 85.3%

Case 2: hit ratio = (6+29)/(8+18+15) * 100 = 85.3%


Reduction to equipartition problem from the partition problem? Equipartition Problem:

Instance: $2n$ positive integers $x_1,\dots,x_{2n}$ such that their sum is even. Let $B$ denote half their sum, so that $\sum x_{i} = 2B$.

Query: Is there a subset $I \subseteq [2n]$ of size $|I| = n$ such that $\sum_{i \in I} x_{i} = B$?

Can the partition problem - same as the above but without the restriction on $|I|$ -  be reduced to the above problem ?

As noted in the comments, the EQUIPARTITION problem is also NP-complete. The basic idea of reducing PARTITION to it is to add elements so that they can be partitioned complementary to the original elements (thus yielding an equipartition) but in a way that ensures that new and old elements can not cancel each other out. The latter can be achieved by choosing the new elements sufficiently large.

Let $A = \{a_1, \dots, a_n\} \subseteq \mathbb{N}_+$ be an instance of PARTITION. Construct an instance $f(A)$ of EQUIPARTITION by

$\qquad \displaystyle f(A) = A \cup \{ a_{n+i} \mid a_{n+i} = 2B \cdot a_i, a_i \in A \}$

with $2B = \sum_{a \in A} a$. It is clear that $f$ can be computed in deterministic polynomial time. We have to show that $A$ is a YES-instance of PARTITION if and only if $f(A)$ is a YES-instance of EQUIPARTITION.

Let $A$ be a YES-instance of PARTITION, that is there is $I \subset [n]$ with $\sum_{i \in I} a_i = B$. Then,

$\qquad \displaystyle I' = I \cup \{n+i \mid i \in \overline{I} = [n] \setminus I \}$

is a solution of $f(A)$; note that $|I'| = n$ and $\sum_{i \in I'} a_i = B + 2B^2 =  \sum_{i \in \overline{I'}} a_i$. Thus, $f(A)$ is a YES-instance of EQUIPARTITION.
Let $f(A)$ be a YES-instance of EQUIPARTITION. Let $I' = I \cup J$ a solution of $f(A)$ with $I \subseteq [n]$ and $J \subseteq [2n] \setminus [n]$ ($I$ contains the indices chosen from $A$, $J$ the new ones), and $\overline{I'} = \overline{I} \cup \overline{J}$ its complement, similarly partitioned. That is, $\sum_{i \in I'} a_i = \sum_{i \in \overline{I'}} a_i$

Assume towards a contradiction that $\sum_{i \in I} a_i \neq \sum_{i \in \overline{I}} a_i$; without loss of generality assume $\sum_{i \in I} a_i > \sum_{i \in \overline{I}} a_i$. Now we have that

$\qquad \displaystyle 0 < \sum_{i \in \overline{J}} a_i - \sum_{i \in J} a_i = \sum_{i \in I} a_i - \sum_{i \in \overline{I}} a_i < 2B$

which contradicts the construction of $f(A)$; elements with indices in $J \cup \overline{J}$ are all (positive) multiples of $2B$ so the assumed difference is impossible. Therefore, $I$ is a solution of $A$ which is thus a YES-instance of PARTITION.

This concludes the proof, that is PARTITION $\leq_p$ EQUIPARTITION by virtue of $f$.