# Question
Title: How do I use message passing to find the maximum of all values in a grid?
I am working on a problem. I have been tracing much more simple problems by hand, but I got this one and I am truly at a loss. I do not know how to research this to help me figure it out. I am truly at a loss as to how to begin writing the message passing code to solve this. Any help on knowing how to break this problem down would be greatly appreciated.

**The question is as follows:**

> Suppose $N^2$ processes are arranged in an $N$ by $N$ square grid. $P\_{i j}$ refers to at the grid position (row $i$, column $j$). A process can communicate, using message passing, only with its neighbors to the left and right, and above and below. (Processes on the corners have only two neighbors; others on the edges of the grid have three neighbors.) Every process has a local integer value $v\_{i j}$. **Show an efficient computation scheme at each of the nodes that will eventually result in every process knowing the maximum of all values in the grid.**

# Answer
> 2 votes
Since the processes can only receive message from their adjacent neighbors, we could first have the all the processes propagate the maximum values through the grid in downward direction in parallel. Similar to a one dimensional array in which we have to find the maximum value. But here, we do that in parallel for n columns of processes.

After this, the last row would contain the maximum values of each column. Then, we could have the last row propagate the maximum value in the right direction so that the (n,n)th element contains the maximum value from this row. Since this row contained the maximum values from each column, (n,n)th element will essentially possess the maximum value from the entire grid.

We could then choose to propagate this value through the grid in parallel backwards till all the nodes know about this maximum value.

Complexity will be O(n) and there will be 4n hops of message passing through this proposed scheme.

**Edit:** Here's A pseudo-code. Disclaimer: not tested, might contain bugs

```
findMaxAllThreads(){
    int maxVal;

    // At the start, each element's max value will exactly be its value itself.
    maxVal = procId.val;

    // If this is the first element in the column, simply send the current
    // max value to the next element within the column.
    if(procId.row == 1)
        sendMessage(procId.row + 1, procId.col, maxVal);

    // For any other element in a particular column, except the last one,
    // compare the received value with the current max value and send the
    // updated value to the next element.
    else if(procId.row < n)
    {
        // wait for the message from the previous element in the column.
        recvMessage(procId.row - 1, procId.col, val);

        // update the max value till this node.
        if(val > maxVal)
            maxVal = val;

        // send the updated max value to the next element in the column.
        sendMessage(procId.row + 1, procId.col, maxVal);
    }

    // If we reach the last element in the column, we need to propagate the
    // values rightwards to the next element within the last row.
    else
    {
        // Receive the message from the (n-1)th element in the column.
        recvMessage(procId.row - 1, procId.col, val);

        // update the max value. Note that this will be the maximum value of
        // this particular column.
        if(val > maxVal)
            maxVal = val;

        // If this is the (n,1)th element in the whole grid (bottom left), then
        // simply propagate the max value to the next element rightwards in the
        // row.
        if(procId.col == 1)
            sendMessage(procId.row, procId.col + 1, maxVal);
        else
        {
            // Wait for the value from the previous element in this row.
            recvMessage(procId.row, procId.col - 1, val);

            // Update the max value till now.
            if(val > maxVal)
                maxVal = val;

            // If this is not the (n,n)th element in the grid, propagate the
            // value to the right.
            if(procId.col != n)
            {
                // Propagate the max value to the right.
                sendMessage(procId.row, procId.col + 1, maxVal);
            }

            // if this is the bottom-right (n,n)th element in the grid, wait
            // for the final value arriving from  the (n, n-1)th element from
            // the left.
            else
            {
                // Receive the message from the (n-1)the element in the nth row.
                recvMessage(procId.row, procId.col - 1, val);

                // Update the value. Note that this is also the maximum value
                // in the entire grid.
                if(val > maxVal)
                    maxVal = val;

                // Now maxVal contains the maximum value from all the processes.
                // We could choose to report it or if we want, we could
                // propagate it all the way back to the first node, so that
                // it's known globally as the max value.
            }
        }
    }
}

```

---
Tags: algorithms, distributed-systems, parallel-computing, message-passing
---


title: NP Complete Clique Variation

text:
# Question
Title: NP Complete Clique Variation
I have the following problem I am trying to prove NP Complete.

Tutors have two jobs- grading exams and homework help. Suppose we have a set of $n$ tutors. Each of them can tutor any amount of $m$ classes.

The tutors rent a large study room to offer help to students. But, note that ALL tutors for a specific class can't be in the study room. Otherwise, that class will have no one left to grade the exams.

Question is, can we have $k$ tutors in the study room?

Attempt at solution:

I feel like this is a set or vertex cover problem and have interpreted as follows. We create a bipartite graph... connecting the left hand side (class) to right hand side (tutor). We have to see if we can choose $k$ tutors from the right hand side such that no left hand side vertex has all its edges used up.

For example, if $k = 1$ the answer is yes. Choose any person. If $k = 2$ answer is yes. $\\{A, D\\}$ works but not $\\{A, B\\}$ because they make up the tutors for $C2$. $k = 3, 4$ also do not work for the same reasoning.

I am trying to decide if I should approach this with set-covers, clique, independent set? I'm not entirely sure but feel this approach is on the right track.

# Answer
> 1 votes
You can prove this by a reduction from the Hitting Set problem (which is NP-Complete):

> Given a base set $U$, a family $F = \\{S\_1,\ldots,S\_\ell\\}$ of subsets of $U$ and an integer $q$, decide if there exists a set $H$ of size at most $q$ which intersects every set in $F$ (this is called a hitting set).

So suppose given an instance of the Hitting Set problem. For every element in $u\in U$, create a new TA $T\_u$. For every set $S\in F$, create a new class $C\_S$ whose TAs correspond to the elements in $S$. Let $k = |U|-q$.

Then if you interpret the TAs being left out of the room as the elements chosen in $H$ it is not hard to see that there exists a hitting set of size at most $q$ if and only if you can put $k$ TAs in the room. That is because putting $k = |U|-q$ TAs in the room is equivalent to leaving at most $q$ outside of the room. And hitting every set in $F$ is equivalent to having at least one TA per class left out of the room.

(I leave the formal proof up to you)

---
Tags: algorithms, graphs, np-complete
---


# Question
Title: Can someone pelase give a counter example of it? If a problem is in NP then there is no known polynomial time algorithm to solve it
Is there any known polynomial time algorithm to solve a problem which that problem is in NP. I was told is False but can't think of any counter example now.

# Answer
NP is the class of decision problems where any instance with an answer "YES" has a proof that the answer is YES which can be checked in polynomial time. NP contains all problems that are solvable in polynomial time. Therefore there are many problems in NP with known polynomial time algorithms.

If you are talking about NP-complete problems, that's a whole different matter. There is (at this point in time) no NP-complete problem with a known polynomial time algorithm to solve it.

Someone might find a proof that for an NP-complete problem there is no NP-complete problem with a polynomial time algorithm to solve it - not just no known algorithm, but no algoritm at all.

On the other hand someone might actually find an NP-complete that can be solved in polynomial time. It is unlikely though.
> 0 votes

---
Tags: np-complete, np, proof-assistants
---


# Question
Title: Is Category Theory useful for learning functional programming?
I'm learning Haskell and I'm fascinated by the language. However I have no serious math or CS background. But I am an experienced software programmer.

I want to learn category theory so I can become better at Haskell.

Which topics in category theory should I learn to provide a good basis for understanding Haskell?

# Answer
In a previous answer in the Theoretical Computer Science site, I said that category theory is the "foundation" for type theory. Here, I would like to say something stronger. *Category theory is type theory*. Conversely, *type theory is category theory*. Let me expand on these points.

**Category theory is type theory**

In any typed formal language, and even in normal mathematics using informal notation, we end up declaring functions with types $f : A \to B$. Implicit in writing that is the idea that $A$ and $B$ are some things called "types" and $f$ is a "function" from one type to another. Category theory is the algebraic theory of such "types" and "functions". (Officially, category theory calls them "objects" and "morphisms" so as to avoid treading on the set-theoretic toes of the traditionalists, but increasingly I see category theorists throwing such caution to the wind and using the more intuitive terms: "type" and "function". But, be prepared for protests from the traditionalists when you do so.)

We have all been brought up on set theory from high school onwards. So, we are used to thinking of types such as $A$ and $B$ as sets, and functions such as $f$ as set-theoretic mappings. If you never thought of them that way, you are in good shape. You have escaped set-theoretic brain-washing. Category theory says that there are many kinds of types and many kinds of functions. So, the idea of types as sets is limiting. Instead, category theory axiomatizes types and functions in an algebraic way. Basically, that is what category theory is. A theory of types and functions. It does get quite sophisticated, involving high levels of abstraction. But, if you can learn it, you will acquire a deep understanding of types and functions.

**Type theory is category theory**

By "type theory," I mean any kind of typed formal language, based on rigid rules of term-formation which make sure that everything type checks. It turns out that, whenever we work in such a language, we are working in a category-theoretic structure. Even if we use set-theoretic notations and think set-theoretically, still we end up writing stuff that makes sense categorically. That is an *amazing fact*.

Historically, Dana Scott may have been the first to realize this. He worked on producing semantic models of programming languages based on typed (and untyped) lambda calculus. The traditional set-theoretic models were inadequate for this purpose, because programming languages involve unrestricted recursion which set theory lacks. Scott invented a series of semantic models that captured programming phenomena, and came to the realization that typed lambda calculus exactly represented a class of categories called *cartesian closed categories*. There are plenty of cartesian closed categories that are not "set-theoretic". But typed lambda calculus applies to all of them equally. Scott wrote a nice essay called "Relating theories of lambda calculus" explaining what is going on, parts of which seem to be available on the web. The original article was published in a volume called "To H. B. Curry: Essays on Combinatory Logic, Lambda Calculus and Formalism", Academic Press, 1980. Berry and Curien came to the same realization, probably independently. They defined a categorical abstract machine (CAM) to use these ideas in implementing functional languages, and the language they implemented was called "CAML" which is the underlying framework of Microsoft's F#.

Standard type constructors like $\times$, $\to$, $List$ etc. are *functors*. That means that they not only map types to types, but also functions between types to functions between types. *Polymorphic functions* preserve all such functions resulting from functor actions. Category theory was invented in 1950's by Eilenberg and MacLane precisely to formalize the concept of polymorphic functions. They called them "natural transformations", "natural" because they are the only ones that you can write in a type-correct way using type variables. So, one might say that category theory was invented precisely to formalize polymorphic programming languages, even before programming languages came into being!

A set-theoretic traditionalist has no knowledge of the functors and natural transformations that are going on under the surface when he uses set-theoretic notations. But, as long as he is using the type system faithfully, he is really doing categorical constructions without being aware of them.

---

All said and done, category theory is the quintessential mathematical theory of types and functions. So, all programmers can benefit from learning a bit of category theory, especially functional programmers. Unfortunately, there do not seem to be any text books on category theory targeted at programmers specifically. The "category theory for computer science" books are typically targeted at theoretical computer science students/researchers. The book by Benjamin Pierce, Basic category theory for computer scientists is perhaps the most readable of them.

However, there are plenty of resources on the web, which are targeted at programmers. The Haskellwiki page can be a good starting point. At the Midlands Graduate School, we have lectures on category theory (among others). Graham Hutton's course was pegged as a "beginner" course, and mine was pegged as an "advanced" course. But both of them cover essentially the same content, going to different depths. University of Chalmers has a nice resource page on books and lecture notes from around the world. The enthusiastic blog site of "sigfpe" also provides a lot of good intuitions from a programmer's point of view.

The basic topics you would want to learn are:

* definition of categories, and some examples of categories
* functors, and examples of them
* natural transformations, and examples of them
* definitions of products, coproducts and exponents (function spaces), initial and terminal objects.
* adjunctions
* monads, algebras and Kleisli categories

My own lecture notes in the Midlands Graduate School covers all these topics except for the last one (monads). There are plenty of other resources available for monads these days. So that is not a big loss.

The more mathematics you know, the easier it would be to learn category theory. Because category theory is a general theory of mathematical structures, it is helpful to know some examples to appreciate what the definitions mean. (When I learnt category theory, I had to make up my own examples using my knowledge of programming language semantics, because the standard text books only had mathematical examples, which I didn't know anything about.) Then came the brilliant book by Lambek and Scott called "Introduction to categorical logic" which related category theory to type systems (what they call "logic"). It is now possible to understand category theory just by relating it to type systems even without knowing a lot of examples. A lot of the resources I mentioned above use this approach to explain category theory.
> 134 votes

# Answer
Echoing @AJed advice, I recommend to turn your statement

```
I want to learn category theory so I can become better at Haskell.

```

on its head: learn Haskell, building on your programming intuition. Once you are an FP guru, it might be easier to pick up category theory (if you still care).

Category theory is simple for somebody with broad mathematical education (groups, rings, modules, vector spaces, topology etc). Lacking this background, category theory is nearly impenetrable. The beauty of category theory is that it unifies a lot of seemingly unrelated things (e.g. left adjoints of forgetful functors include free groups, universal enveloping algebras, Stone-Cech compactifications, abelianisations of groups, ...), and so reduces complexity. But if you are not familiar with the multiple examples that category theory unifies, category theory is just an additional layer of complexity that makes your life harder.

In my experience, learning is easier by building on things one already knows. As a software developer, you know a lot about programming, and Haskell programming is not that different from other programming, so my recommendation is to approach Haskell from a pragmatic programming point of view, ignoring category theory. The bit of category theory that is in Haskell, e.g. some support for monads, is much easier for a programmer to grasp without taking a detour via category theory. After all, monads are merely generalised composition (and you will have used monads in your programming practise already -- albeit without knowing you did), and Haskell doesn't really support monads for real, as it does not enforce the monadic laws.
> 36 votes

# Answer
I'm going to try and keep it short and sweet. There is an informal correspondence between Haskell programs and certain classes of categories, which can be made more formal with some work. This correspondence is known as the Curry-Howard-Lambek correspondence and relates:

1. Haskell *types* with *objects* of the category
2. *Terms* of type $A\rightarrow B$ with *morphisms* $f\colon A\rightarrow B$ (note the similar notations)
3. *Algebraic datatypes* with *initial objects*
4. *Type constructors* with *functors*
5. etc

The list goes on and on, but one crucial point is that you can define things like monads and algebras in category theory and come up with notions that are both useful to mathematicians but also pervasive in the practice of Haskell programming.

I'm not sure which book to recommend, as I haven't found a completely satisfactory introductory book on categories for computer scientists. You can try Categories, Types and Structues by Asperti and Longo. The idea is to learn basic definitions up to adjunctions, and then maybe try and read some of the excellent blogs out there to try and understand these concepts.
> 32 votes

# Answer
A short answer: no \[but this is only an opinion\]

Don't go to Category Theory or any other theoretical domain to become good in Haskell. Learn functional programming techniques, such as tail recursion, map, reduce, and others. Read as much code as you can. Implement as many ideas as you can. If you have issues, read and read.

If you want a good *theoretical reference* to learn Haskell and other functional programming paradigms then have a look at: An Introduction to Functional Programming Through Lambda Calculus, Greg Michaelson (available online). ... There are other similar books.
> 15 votes

# Answer
Category theory is not a good basis for understanding Haskell. Category theory has certain but limited use for learning functional programming and in actual practice of functional programming. I recently made a presentation to answer the question "What did category theory ever do for us (functional programmers)". See https://www.youtube.com/watch?v=Zau8CxsfxOo

Summary of the talk:

* Functional programmers do not require category theory in order to master the main features and design patterns that FP uses to write better code. For example, one can (and should) first learn how to use monads, functors, map/filter/fold, pattern matching, recursive algebraic data types, etc., in a concrete programming language with specific examples. Category theory will not help master these techniques even though the words "functor" and "monad" originally come from category theory.
* At a certain point, programmers will see examples of typeclasses with laws, and understand why those laws are important in practice.
* There will be lots of different laws. To make some order and system among those laws, we can formulate the laws as a generalized "lifting" type signature with "twisted" function types. At this point, it becomes useful to talk about categories, morphisms, and functors.
* We can then use the definitions of category and functor as generalizations that explain the laws of functors, contrafunctors, filterable functors, filterable contrafunctors, monads, applicative functors, applicative contrafunctors, comonads, and perhaps other type classes.
* I show some examples of categories that are used to describe functors, monads, applicatives, and filterable functors.
* I cover filterable functors in more detail, with backdrop of category theory, because filterable functors are rarely explained as a separate typeclass.
* Another example where category theory is useful: "type constructor libraries", i.e. libraries with functions parameterized by a *type constructor*. Examples of these are free functor / free monad / etc., and Church encoding of types (including recursive type constructors, e.g. the Church encoding of a free monad). Programmers who need to implement these libraries will need to understand how these constructions are defined and what laws need to hold. Category theory provides some limited guidance about that.
* Conclusion 1: programmers need to learn functional programming and not category theory. The special knowledge required in functional programming (e.g., how to implement and use a free applicative functor in your programming language) is not going to be covered by any book in category theory.
* Conclusion 2: basic definitions of category theory (category, functor, natural transformation) are useful as condensed formulations of general laws for a number of typeclasses. Unless a programmer has experience dealing with all the different laws of those typeclasses, it is unlikely that an appreciation of category theory will be of much help. Even for advanced programmers who are working with high-level type constructor libraries, a study of category theory is unlikely to be of any use beyond a few basic concepts and definitions (category, functor, natural transformation, monoid, initial object, Yoneda identities, F-algebra).
* Conclusion 3: knowledge of category theory will not help us derive or prove laws for specific typeclasses, and will not help us implement those typeclasses correctly in code. The reason is that category theory is so general that it only talks about laws that apply generally to a large number of very different typeclasses (functor, monad, filterable functor, applicative functor, pointed functor, contravariant functor, etc.). For practical coding, e.g. to verify that our implementation of a specific monad is lawful, we need to learn not category theory but the techniques of symbolic derivation and proof.

I am writing a new free textbook ("Science of Functional Programming", https://github.com/winitzki/sofp) to develop and explain these techniques with practical programmers in mind. My book is going to be very light on category theory, and I'm not going to use any advanced abstract concepts unless there is a significant gain for practical work. Having written down several hundred step-by-step proofs, I have found what derivation techniques are useful and what definitions from category theory are helpful when proving the theoretical properties of practically relevant code.

Examples of category theory knowledge that has, so far, proved to be unnecessary and **not useful**:

* monad is a monoid in the category of endofunctors
* any monad comes from a pair of adjoint functors
* a free monad comes from the free/forgetful functor adjunction

In contrast, naturality laws are used in at least 30% of all proofs, and the functor composition law is also used in at least 30% of proofs. This shows the importance of learning the definitions of functors and natural transformations and getting some intuition about how to use those notions for programming.
> 3 votes

# Answer
Here is a (long) blog post, that gives motivation on how category theory ideas are relevant for practical programming: http://cdsmith.wordpress.com/2012/04/18/why-do-monads-matter/
> 2 votes

# Answer
Category theory is a very sophisticated branch of mathematics and mastering it will unify most of your previous learnings by making them instances of same abstract objects. So it is very useful and very intuitive. But it is vast and broad, and you will find yourself in a plenty of new concepts that will don't even know which one is suitable for your needs and which one you should skip. So your purposeful approach needs choice among concepts, otherwise mastering in it inevitably needs long time and is really not a self study domain.

By the way, I suggest a very well start point for your purpose to be here.
> 0 votes

---
Tags: programming-languages, functional-programming, category-theory
---


title: Polynomial bound on sum of strings

text:
# Question
Title: Polynomial bound on sum of strings
I am struggling with the following problem:

Given a set of finite binary strings $S=\\{s\_1,\ldots,s\_k\\}$, we say that a string $u$ is a concatenation over $S$ if it is equal to $s\_{i\_{1}} s\_{i\_{2}} \cdots s\_{i\_{t}}$ for some indices $i\_1,\ldots, i\_t \in \\{1,\ldots, k\\}.$

Your friend is considering the following problem: given two sets of finite binary strings $A=\\{a\_1,\ldots,a\_m\\}$ and $B=\\{b\_1,\ldots , b\_n \\}$, does there exist any string $u$ so that $u$ is both a concatenation over $A$ and a concatenation over $B$?

Your friend announces "at least the problem is in $\mathcal{NP}$, since I would just have to exhibit such a string $u$ in order to prove the answer is yes." You point out that this an inadequate explanation. How do we know the shortest string $u$ doesn't have length exponential in the size of the input?

**Prove the following: If there is a string $u$ that is a concatenation over both $A$ and $B$, then there is such a string whose length is bounded by a polynomial in the sum of the lengths of the strings in $A\cup B$.**

Now, I have actually found a solution and the solution claims that the maximum length of $u$ is at most $n^2L^2$ where we assume $m \leq n$ and $L$ denotes the maximum length of any string in $A \cup B$. The solution then goes on to exhibit a proof by contradiction using the pigeonhole principle to show that if we assume $u$ has length greater than $n^2L^2$ we arrive at a contradiction.

My question is where does the bound $n^2L^2$ come from? I know that $n$ is the number of strings in set $B$ and $L$ is the max length string in $A \cup B$. But I feel as if the largest possible concatenation over both would be more like $2nL$ since we would need to include every string in both $A$ and $B$ and the longest string in either is $L$ and there are at most $n$ strings in each. What am I missing? I think I can handle the remainder of the proof once I understand where the $n^2L^2$ bound is coming from.

# Answer
You can also prove this using automata theory. For a set $S = \\{s\_1,\ldots,s\_k\\}$ of strings over $\Sigma$, consider the following language over $\Sigma \cup \\{1,\ldots,k\\}$: $$ L\_S = (1s\_1+2s\_2+\cdots+ks\_k)^+. $$ This language is accepted by a DFA of size roughly $\\|S\\| := |s\_1|+\cdots+|s\_k|$. The exact size depends on the model of DFA - in our case it makes sense to ask for *at most* one transition out of each state with a given label (rather than *exactly* one transition, as is usually the case).

Now we want to do the same, but for two sets of strings $A = \\{a\_1,\ldots,a\_m\\}$, $B = \\{b\_1,\ldots,b\_n\\}$. To this end, we consider languages $L\_A,L\_B$ which are defined as before, but with two differences:

* $1,\ldots,k$ are replaced with $A\_1,\ldots,A\_m$ for $L\_A$ and $B\_1,\ldots,B\_n$ for $L\_B$.
* The symbols $A\_1,\ldots,A\_m$ are ignored in $L\_B$, and the symbols $B\_1,\ldots,B\_n$ are ignored in $L\_A$.

As an example, suppose that $A = \\{a,ba\\}$ and that $B = \\{ab,a\\}$. Then the following word will be in our language: $A\_1B\_1aA\_2bB\_2a$.

As before, we can construct DFAs for $L\_A,L\_B$ having roughly $\\|A\\|,\\|B|$ states, respectively. Using the product construction, we get a DFA of size roughly $\\|A\\|\cdot\\|B\\|$ for the intersection. It is well-known (and can be proved using the pigeonhole principle) that if a DFA having $N$ states accepts any word, then it accepts some word of size less than $N$. This implies your claim.

---

In terms of lower bounds, it is easy to refute your conjecture that $2nL$ is enough. Consider $A = \\{ 0^L \\}$ and $B = \\{ 0^{L-1} \\}$. It is not hard to check that the minimal solution has length $L(L-1) \approx L^2$.

It's less clear what is the correct dependence on $n$.
> 3 votes

# Answer
I think the intuition is something like this (warning, not very rigorous):

We make two copies of $u$, call them $u\_a$ and $u\_b$, one in terms of the $a\_i$ and one in terms of $b\_i$. We place them side by side as shown. Then we 'break off' the last string of either $u\_a$ or $u\_b$ to make a endpoint, which is probably going to be unequal as shown below.

Now, we keep breaking stuff off, until we get an endpoint that we have seen before.

**How long will this take**? It will be bounded by the number of different endpoints we have. How many such endpoints? We can create all endpoints by choosing some pair of $a\_i$ and $b\_j$, there are $n^2$ such pairs, and then we align them, there are up to $L$ different ways to align them. **So total number of different endpoints is $n^2 L$.**

So we know that if we keep breaking off bits, we will eventually encounter an endpoint that we have seen before. Then we can shorten the original string $u$, by cutting out the portion between the 2 occurrences of the same endpoint. We keep repeating this until $u$ is as short as possible, which would happen once $u$ has no more 'repeated endpoints'.

What is the length of $u$ now? $u$ contains all most $n^2 L$ endpoints, **and each endpoint is at most $L$ characters between them** (because the endpoints are separated by at most one or two blocks), that is a **total length of $n^2 L^2$.**

Could you also post a link to the proof so we can take a look!
> 0 votes

---
Tags: complexity-theory, discrete-mathematics
---


title: Subset sum to 0/1 knapsack

text:
# Question
Title: Subset sum to 0/1 knapsack
How can I translate (i.e. reduce) an arbitrary instance $(S, t)$ of Subset Sum into an instance of 0-1 Knapsack? I'm also given a hint: you may assume that all members of $S$ are positive integers.

# Answer
Set the size of the bag to the value you are trying to reach $t$. For each element $x \in S$ add one item to the set having both its weight and value equal to $x$. The claim is the $(S, t)$ is a yes instance of the subset sums problem if and only if the optimal value of the bag is equal to $t$ (why?).
> 1 votes

---
Tags: algorithms, complexity-theory, np-complete, np-hard, np
---


# Question
Title: Regular expression for strings not starting with 10
How can I construct a regular expression for the language over $\\{0,1\\}$ which is the complement of the language represented by the regular expression $10(0+1)^\*$?

# Answer
> 2 votes
If a word doesn't start with $10$, then either it starts with some other combination of two letters, or it is shorter than two letters. All in all, we get the following regular expression for your language: $$ \epsilon + 0 + 1 + (00+01+11)(0+1)^\*. $$

---
Tags: regular-languages, regular-expressions
---


title: Another Subset sum problem

text:
# Question
Title: Another Subset sum problem
Verify that (S = {83, 88, 93, 67, 57, 89, 78, 51, 95, 98, 69, 49}, t = 492) is a positive instance of Susbset Sum.

# Answer
The set $S$ consists of $12$ numbers. Hence it has $2^{12} = 4096$ subsets.

You can write a computer program that goes over all subsets, sums each of them, and determines whether the sum is $492$, in which case it prints the subset.
> 1 votes

---
Tags: complexity-theory, np-complete, np-hard, np
---


# Question
Title: Proving NP-Complete problem by reduction of subset-sum
My assignment question as "given a multiset of symbols (letters) L from an alphabet Σ (thus, the same letter may appear in L multiple times), and a set of words W ⊆ Σ' , UseAllLetters asks if it is possible to use all letters from L to make words belonging to W. You may form the same word multiple times. Prove that UseAllLetters is NP-complete."

I'm new learning NP problems and still having trouble to understand the intuition behind this. But I'll try my best and sharing my idea here to verify that I'm on the right track.

My suggestion as following:

To prove this question is NP-complete, we can do reduction to subset-sum problem, but we also have to show few things.

1.This problem is in NP. (I'm stuck on this)

2.Any NP-complete problem Y can be reduced to X.

So we choose subset-sum problem, as it defined as:Given a set X of integers and a target number t, find a subset Y ⊆ X such that the member of Y add up to exactly t. Which is similar to our problem, we can find a subset of letters $l$ in our L that make words belonging to W if we are able to find a subset Y ⊆ X such that the member of Y add up to t.

3. The reduction works in polynomial time.
4. UseAllLetters problem has solution iff subset-sum has solution. I'm also stuck on this, it seems like I have to argue the correctness of my reduction, and I'm not sure my reduction is the right way to do it, I just do like one-to-one mapping to subset-sum problem.

Any feedback?

# Answer
To prove a problem is NP-complete you have to prove it is in NP and that it is NP-hard. NP-hardness proof is usually however, a reduction from one NP-hard problem. To prove that the problem is NP, you can either describe a non-deterministic polynomial time algorithm for the problem (An NTM that decides the language of the yes-Instances in polynomial time), or you can show that there is a certificate of polynomial size for each yes-instance, such that given the instance with the certificate you can in polynomial time prove that the instance is a yes instance.

Both ways are quite easy here. A polynomial certificate would be an answer of the problem. You can verify if a given set of words as a solution really uses each letter exactly once. Describing an NTM is also straightforward, where the NTM guesses all possible subsets of words and checks for each subset if it covers all letters and each letter exactly once.

To prove NP-hardness, I suggest a reduction from the Exact-Cover problem instead, since it is more related. In the exact cover problem, you are given a Universe of elements $\mathcal{U}$ and a family of sets $\mathcal{F} = \\{F\_1, \dots F\_n\\}$ over the universe (A set of subsets of the universe). The output is whether there is a subset of the sets in the family that cover the whole universe and each element is covered exactly once (included in exactly one chosen set). A reduction to your problem would be as follows. We set $\Sigma = W = \mathcal{U}$ (each element in $W$ is repeated exactly once). From each set $F \in \mathcal{F}$ we build a word $s$ that contains exactly the elements in the set (in any order).

If the instance of the exact-cover problem is a yes-instance, then there is a subset of the family $\\{F\_{i\_1}, \dots F\_{i\_k}\\}$ that covers each element in the universe exactly ones. The words $s\_{i\_1}, \dots s\_{i\_k}$ we built from these sets cover each element in $W$ exactly once so it is also a yes instance. On the other hand, if the instance of your problem is a yes instance, there is a ste of words $s\_{i\_1}, \dots s\_{i\_k}$ that covers each element in $W$ and hence in $\Sigma$ exactly once. The sets $F\_{i\_1} \dots F\_{i\_k}$ we build the words from cover each element in the universe exactly once.
> 1 votes

---
Tags: complexity-theory, reductions
---


# Question
Title: How are CPU architecture and word size related?
I did lot of research on internet but couldn't get my answer. I want to know what is the difference between the word size and CPU architecture?

For eg.- I read that CPU of 32-bit architecture can address 2^32 memory locations. Now if we consider that one address points to a single byte, then it means we can have memory size of 2^32 Bytes. We can call it byte addressable memory. Now, I also read that word size is the size of register in a CPU, i.e., it is the minimum no. of bits on which a CPU works upon.

So, help me understand here what is the word size of this computer organization? Is it 32-bit or 1 Byte (as memory is byte addressable)?

What if one address could point 2 Bytes of data instead of 1 Byte? What would be word size then?

Consider the following link.

GATE CS Questions on computer organisation

Question no. 3 from this link is as follows-

> A machine has a 32-bit architecture, with 1-word long instructions. It has 64 registers, each of which is 32 bits long. It needs to support 45 instructions, which have an immediate operand in addition to two register operands. Assuming that the immediate operand is an unsigned integer, the maximum value of the immediate operand is

Now, the very first line of the solution says-

> As machine has 32-bit architecture, therefore, 1 word = 32 bits = instruction size

How can we say that since CPU is 32-bit, word size is also 32 bit. Doesn't 32-bit architecture just mean that the no. of addresses in the physical memory is 2^32? And also doesn't the word size mean the size of memory each of those 2^32 addresses would point to?

# Answer
> 3 votes
It's simple - 32 bit word size, or 32 bit architecture, mean exactly what the person using the expression means. No more, no less. You can't draw any conclusions from it.

For example, there's an Intel 32 bit architecture that can address 64 GB of physical RAM, and no Intel 64 bit architecture that can address anything near 2^64 bytes of physical or virtual memory, while 32 bit PowerPC supported 2^53 bytes of virtual memory.

64 bit POWER has 32 bit instructions. 32 bit Intel has instructions from 8 bit to over 100 bit.

32 bit ARM is what it is, and 64 bit ARM is what it is. Some with 32 and 64 bit x86, except they are different. And so on. Don't make any assumptions, they will all be somewhere between wrong and not quite right.

If you want to pass an exam, learn the answers that the exam expects (sad but true).

# Answer
> 1 votes
On the question about what is the meaning of 32 in 32-bit CPU architecture or computer architecture and what is the word size of this computer organization, please check the question and answers at "Is word size, the size of a memory location? the size of the data bus? or the cpu register size?".

Now let us take a look at the Que 3 of GATE CS Questions on computer organisation.

* It reads "A machine has a 32-bit architecture, with 1-word long instructions. It has 64 registers, each of which is 32 bits long". That given specification asks/demands readers to treat 1 word as 32 bits long on that machine. There is no incentive to be extremely exacting or pedantic here.
* The solution line "As machine has 32-bit architecture, therefore, 1 word = 32 bits = instruction size" could have better been "The machine has 32-bit architecture with 32 bits = instruction size" to avoid the debatable connotation that "since CPU is 32-bit, word size is also 32 bit".
* However, that solution line with that connotation is not a glaring error anyway. For most of the computers that we have or we had have before 32-bit CPU do imply 32-bit word size. The majority if not most of the people I believe will take 32-bit word size on 32-bit cpu or computer architecture.
* In fact, it looks like that both the problem and you are distracted by an insignificant issue that is not directly related to the problem proper. I mean, to sidestep the irrelevant word-size issue or to make the word-size issue irrelevant, the problem could just read, "A machine of 32-bit architecture has instruction size as 32 bits. It has 64 registers, each of which is 32 bits long". However, I might be off the right track here since I know nothing about the curriculum of GATE exam. This is just my 2-cent observation as an outsider.

# Answer
> 0 votes
It's simple: n-bit architecture has n bits word length. For example: A 32-bit CPU has word length 4 bytes = 32 bits. The pointer size is the same. Think combinatorically: How many combinations can you point to with n bits?

---
Tags: computer-architecture, cpu
---


# Question
Title: Creating a Deterministic Push-Down Automaton for the Union of two languages
> Suppose, we have $L\_1:=\\{w\in\\{a,b\\}^\*\mid \\#\_a(w) \equiv 0 \mod 4\\}$ and $L\_2:=\\{w\in\\{a,b\\}^\*\mid abaab \text{ is a substring of } w\\}$. Now we want to create a Deterministic Push-Down Automaton for $L\_1\cap L\_2$

I've created PDA's for both languages:

$M'=(Q,\Sigma,\Gamma,\Delta,s,F)$ with $\Sigma=\\{a,b\\}$, $\Gamma=\\{\\}$, $Q=\\{1,2,3,4\\}$, $F=\\{0\\}$, $s=\\{0\\}$ and \begin{align} \Delta=\\{&(0,a,\lambda,1,\lambda),(0,b,\lambda,0,\lambda)(1,a,\lambda,2,\lambda),(1,b,\lambda,1,\lambda),(2,a,\lambda,3,\lambda),(2,b,\lambda,2,\lambda)\\ &(3,a,\lambda,0,\lambda),(3,b,\lambda,3,\lambda)\\} \end{align} where $\Delta\subseteq Q\_{old}\times (\Sigma \cup \\{\lambda\\})\times(\Gamma\cup \lambda)\times Q\_{new}\times\Gamma^\*$

and

$M''=(Q,\Sigma,\Gamma,\Delta,s,F)$ with definitions above and $\Sigma=\\{a,b\\}$, $\Gamma=\\{\\}$, $Q=\\{1,2,3,4,5,6\\}$, $F=\\{6\\}$, $s=\\{1\\}$ and \begin{align} \Delta=\\{&(1,a,\lambda,2,\lambda),(1,b,\lambda,1,\lambda),(2,a,\lambda,2,\lambda),(2,b,3,\lambda),(3,a,\lambda,4,\lambda),(3,b,\lambda,1,\lambda),\\\&(4,a,\lambda,5,\lambda),(4,b,\lambda,3,\lambda),(5,a,\lambda,2,\lambda),(5,b,\lambda,6,\lambda),(6,a,\lambda,6,\lambda),(6,b,\lambda,6,\lambda)\\} \end{align}

$M'$ accepts $L\_1$ and $M''$ accepts $L\_2$, but how to construct $M^{\star}=M'\cap M''$ which accepts $L\_1\cap L\_2$?

I know, that we could possibly do this with Deterministic Finite Automata, but I want to know how it would work with PDA's.

# Answer
There is no general algorithm for computing a DPDA $M^\*$ as the intersection of two DPDA $M,M'$; that problem is undecidable. See Undecidable problem intersection of two DCFL languages is DCFL? for a proof.

So, you will have to look for some pattern in this particular problem that makes it easier than the general case. Hint: what level in the Chomsky hierarchy is $L\_1$ at? what about $L\_2$?
> 2 votes

---
Tags: context-free, pushdown-automata
---


title: doubt in pipelining

text:
# Question
Title: doubt in pipelining
I am not from cse but trying to learn computer architecture on my own. Please clarify the following.

> 1. In case of pipelining, each stage or subcomponent or subtask is assumed to be done in 1 CPU clock cycle time. Why is it so?

some operations may exceed 1 cpu clock cycle time. I am visualising pipelining as series of operations like assembly line in a factory.

> 2. Micro-operation(phases of instruction) is also assumed to be performed in 1 cpu clock cycle. How is it possible? what if some task may exceed 1 cpu clock cycle time.

# Answer
There are two possibilities:

1. No operation is allowed to take longer than one clock cycle. If the designers of the CPU can't fit an operation into one clock cycle, then either the clock cycle must be made longer, or that operation must be split into two, or they designers work extra hard to make that operation faster. That's the more common way to do this.

(Obviously making the clock cycle longer is something that you really, really don't want to do.)

2. We remove the assumption that every operation must be done in one clock cycle. If we encounter an operation that cannot be done in one cycle, then this operation stalls the pipeline. One clock cycle will be lost. This method may be used for operations that almost always run in one clock cycle, but in very very rare cases take longer. I remember the PowerPC 603 doing this when a floating point multiplication produced a result that was denormalised but not zero.

In your visualisation with an assembly line: If a worker figures out that he can't do his job fast enough then he presses a red button that stops the assembly line, finishes his job, then presses a green button to get the assembly line running.
> 3 votes

---
Tags: computer-architecture, operating-systems
---


# Question
Title: Minimum edge weight k-exact cover with triangle inequality
Suppose you have a weighted graph $G = (V, E \subseteq V^2, w \in E \to \mathbb{R}^+)$, where $w$ satisfies the triangle inequality $w(x, y) + w(y, z) \ge w(x, z)$. Suppose $k \in \mathbb{N}$ (in practice, $k \le 6$ is common). I want to find a set $C \subseteq \mathbb{P}(V)$ (a set of subsets of $V$) such that:

1. $\max\_{I \in C} \sum \\{w(x, y) \mid x \in I \wedge y \in I\\}$ is minimized.
2. For all $I \in C$, $\mathrm{card}(I) = k$.
3. No two elements of $C$ have nonempty intersection.
4. The union of all elements of $C$ is $V$.

Assume that $\mathrm{card}(V) = r \cdot k$ for some $r \in \mathbb{N}$.

Is there a polynomial-time approximation algorithm for this task?

I believe this problem is related to facility location problems, but I am not sure.

# Answer
Let $n := |V| = rk$ be the total number of vertices in the graph. Basically, we are looking for a partition of $V$ into $r$ sets each of size $k$. The total cost will be then the sum of the weights of all edges present in the graph induced by each of these sets. Note that the edges having one end in one of these sets and the other endpoint in another set form together an $r$-cut and are exactly the edges we do not count in our sum. Hence, instead of minimizing the sum of edges in the subgraphs induced by the sets of the partition, we can maximize the weights of edges having one end in a set of the partition and the other end in a different set.

Note that we are looking here at a special variation of maximum $k$-cut, where we require that all the subsets of the partition have equal sizes and hence the problems are not completely equivalent. However, it is not hard to reduce the maximum $k$-cut problem (let us call it for now maximum $s$-cut to avoid confusion) to your problem, where given an instance of the $s$-cut problem (with $N$ vertices), you can add $(s-1)N$ additional vertices to the graph and connect each of them with all vertices in the graph with edges of weight 0. Set $k = N$ (note that $n = sN$) and hence, we will have $r = s$. Each solution to your problem corresponds to a solution to the maximum cut problem with dummy vertices assigned arbitrarily to make the count consistent.

The maximum cut problem is APX-hard and hence does not admit PTAS (polynomial time approximation scheme) unless P=NP. Using the previous reduction, and since the maximum cut problem is a special case of the maximum $k$-cut problem, your problem is at least as hard as the maximum cut problem.
> 3 votes

---
Tags: algorithms, graphs, approximation, weighted-graphs
---


# Question
Title: Finding a vertex coverage that is also an independent set
Given a graph $G$ and integer $k$, find a vertex coverage set of size $k$ that is also an independent set. I need to either prove this problem is np-complete or find a polynomial solution. Any idea?

# Answer
This problem is called the independent vertex cover problem and it is solvable in polynomial time. Note that the set $S$ must be a vertex cover means that each edge has an endpoint in the set. On the other side, being an independent set means that each edge has at most one endpoint in the set. Hence, each edge has exactly one endpoint in the set. That means we are looking for the smallest possible subset of vertices $S$ such that $(S, V\setminus S)$ is a bipartition of the graph. This can be done in linear time since each connected component has either non or exactly one bipartition.

Here is also another solution of the problem based on a reduction to the 2-sat problem (also using the fact that each edge has exactly one endpoint in the set).

https://cstheory.stackexchange.com/questions/36707/smallest-vertex-cover-which-is-also-an-independent-set
> 0 votes

---
Tags: algorithms, complexity-theory, graphs, np-complete
---


# Question
Title: Maximum Independent Set of a Bipartite Graph
I'm trying to find the Maximum Independent Set of a Biparite Graph.

I found the following in some notes **"May 13, 1998 - University of Washington - CSE 521 - Applications of network flow"**:

> **Problem:**
>
> Given a bipartite graph $G = (U,V,E)$, find an independent set $U' \cup V'$ which is as large as possible, where $U' \subseteq U$ and $V' \subseteq V$. A set is independent if there are no edges of $E$ between elements of the set.
>
> **Solution:**
>
> Construct a flow graph on the vertices $U \cup V \cup \\{s,t\\}$. For each edge $(u,v) \in E$ there is an infinite capacity edge from $u$ to $v$. For each $u \in U$, there is a unit capacity edge from $s$ to $u$, and for each $v \in V$, there is a unit capacity edge from $v$ to $t$.
>
> Find a finite capacity cut $(S,T)$, with $s \in S$ and $t \in T$. Let $U' = U \cap S$ and $V' = V \cap T$. The set $U' \cup V'$ is independent since there are no infinite capacity edges crossing the cut. The size of the cut is $|U - U'| + |V - V'| = |U| + |V| - |U' \cup V'|$. This, in order to make the independent set as large as possible, we make the cut as small as possible.

So lets take this as the graph:

```
A - B - C
    |
D - E - F

```

We can split this into a bipartite graph as follows $(U,V)=(\\{A,C,E\\},\\{B,D,F\\})$

We can see by brute force search that the sole Maximum Independent Set is $A,C,D,F$. Lets try and work through the solution above:

So the constructed flow network adjacency matrix would be:

$$\begin{matrix} & s & t & A & B & C & D & E & F \\ s & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ t & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ A & 1 & 0 & 0 & \infty & 0 & 0 & 0 & 0 \\ B & 0 & 1 & \infty & 0 & \infty & 0 & \infty & 0 \\ C & 1 & 0 & 0 & \infty & 0 & 0 & 0 & 0 \\ D & 0 & 1 & 0 & 0 & 0 & 0 & \infty & 0 \\ E & 1 & 0 & 0 & \infty & 0 & \infty & 0 & \infty \\ F & 0 & 1 & 0 & 0 & 0 & 0 & \infty & 0 \\ \end{matrix}$$

Here is where I am stuck, the smallest finite capacity cut I see is a trivial one: $(S,T) =(\\{s\\},\\{t,A,B,C,D,E,F\\})$ with a capacity of 3.

Using this cut leads to an incorrect solution of:

$$ U' = U \cap S = \\{\\}$$ $$ V' = V \cap T = \\{B,D,F\\}$$ $$ U' \cup V' = \\{B,D,F\\}$$

Whereas we expected $U' \cup V' = \\{A,C,D,F\\}$? Can anyone spot where I have gone wrong in my reasoning/working?

# Answer
The complement of a maximum independent set is a minimum vertex cover.

To find a minimum vertex cover in a bipartite graph, see König's theorem.
> 15 votes

# Answer
The solution given is clearly incorrect, as you demonstrate with the counterexample. Note that the graph U+V is a connected component by the infinite-capacity edges. Therefore every valid cut will have to contain all of A, B, C, D, E, F on the same side.

Trying to trace back where the solution came from: http://www.cs.washington.edu/education/courses/cse521/01sp/flownotes.pdf cites Network Flows, by Ahuja, Magnanti, and Orlin for *some* of the problems. This book is out of copyright and downloadable from http://archive.org/details/networkflows00ahuj but it doesn't seem to contain this problem and solution (searching for every occurrence of "bipartite").

Note that the explanation paragraph of the solution does not show that the smallest cut of the graph it constructs corresponds to the *maximum* independent set. It only shows a way to get *an* independent set.

And yet, you can see what the algorithm is trying to do. Here is what the actual maximum independent set corresponds to in terms of its s,t cut:

The infinite-capacity edge that breaks the algorithm is emphasised.

I'm not sure how to fix the algorithm to what was intended. Maybe the cost of an infinite edge should be zero if it goes backwards (i.e. where it goes from S to T, but crosses from t-side to s-side)? But is it still easy to find the min-cut/max-flow with this nonlinearity? Also, thinking of a way to bridge from @Jukka Suomela's solution to the algorithm from the question, there is a difficulty where we go from the maximum matching to the minimum vertex cover: while finding the maximum matching can be done by a max-flow-like algorithm, how do you recover the minimum vertex cover from it using a flow-like algorithm? As described here, after the maximum matching is found, the edges between U and V become directed to find the minimum vertex cover. So, again, this doesn't show that a simple application of min-cut/max-flow is all it takes to solve this problem.
> 5 votes

# Answer
The given algorithm is correct. The flow network constructed need to be directed, and the value of a $S$-$T$ cut only considers edges going out of the vertex set $S$.
> 2 votes

# Answer
The cut should be on the actual flow, not on the capacities. Since the flow from s is finite, any {S,T} cut will be finite. The rest is a explained above.
> 0 votes

# Answer
I think that you don't need to connect the edges both ways even if the original graph was undirected. Because for the flow network, you need a directed graph, you could consider only the edges from $U$ to $V$.

Then in this new graph $G'$, you will have a min-cut of 2, which gives you the answer $\\{A,C,D,F\\}$.
> 0 votes

---
Tags: algorithms, graphs, network-flow
---


# Question
Title: Is checking if the length of a C program that can generate a string is less than a given number decidable?
I was given this question:

Komplexity(S) is the length of the smallest C program that generates the string S as an output. Is the question "Komplexity(S) \< K" decidable?

With respect to decidability, I only know about the Halting Problem and just learned about Rice's Theorem while searching online (though I don't think it can be applied here?). I couldn't reduce the problem to any undecidable problem I know about. Thanks in advance for any help

# Answer
> 1 votes
The length of the smallest C program that generates a given string is known as the Kolmogorov complexity of the string. One of the basic properties of Kolmogorov complexity is its undecidability.

---
Tags: computability, undecidability, halting-problem
---


# Question
Title: Why is $T(n)=3T(n/4) + n\log n$ solvable with Master Method but $T(n)=2T(n/2) + n\log n$ is not?
I am having difficulties in understanding why the recurrence

$$T(n)=3T(n/4) + n\log n$$

is solvable with Master Method but

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

isn't?

Despite they both look very similar except the values of coefficient '$a$' and size cutter '$b$'.

I understand that the work function '$f(n)$' must be polynomially larger/smaller than $n^{\log\_ba}$. And that in second recurrence $n^{\log\_22}=n$ is not polynomially comparable to $f(n)=n\log n$. So Master Method cannot be applied. But why can it be applied to the first recurrence?

I found these examples in CLRS Intro to Algo book, and can't understand them. Can you please explain.

# Answer
Let us use the master theorem as stated on Wikipedia. Consider a recurrence $$ T(n) = aT(n/b) + f(n). $$ There are several cases to consider:

1. If $f(n) = O(n^c)$ for $c \< \log\_b a$ then $T(n) = \Theta(n^{\log\_b a})$.
2. If $f(n) = \Theta(n^{\log\_b a} \log^k n)$ for $k \geq 0$ then $T(n) = \Theta(n^{\log\_b a} \log^{k+1} n)$.
3. If $f(n) = \Omega(n^c)$ for $c \> \log\_b a$ and $f(n)$ is "reasonable" then $T(n) = \Theta(f(n))$.

In the third case, a function is "reasonable" if there exist $k \< 1$ and $N$ such that for $N \geq n$, we have $af(n/b) \leq kf(n)$.

There are also extensions of the second case that handle all values of $k$:

1. If $f(n) = \Theta(n^{\log\_b a} \log^k n)$ for $k \> - 1$ then $T(n) = \Theta(n^{\log\_b a} \log^{k+1} n)$.
2. If $f(n) = \Theta(n^{\log\_b a} \log^k n)$ for $k = - 1$ then $T(n) = \Theta(n^{\log\_b a} \log\log n)$.
3. If $f(n) = \Theta(n^{\log\_b a} \log^k n)$ for $k \< - 1$ then $T(n) = \Theta(n^{\log\_b a})$.

---

Now back to your recurrences. The values of $a,b$ and $f(n)$ are:

1. $a=3$, $b=4$, $f(n) = n\log n$.
2. $a=2$, $b=2$, $f(n) = n\log n$.

In the first recurrence, $f(n) = \Omega(n^1)$, where $1 \> \log\_4 3$, and so, according to the third case of the master theorem, $f(n) = \Theta(n\log n)$ (you have to check that the function $n\log n$ is reasonable).

In the second recurrence, $f(n) = \Theta(n^1 \log^1 n)$, where $1 = \log\_2 2$, and so, according to the second case of the master theorem, $f(n) = \Theta(n\log^2 n)$.
> 1 votes

---
Tags: algorithm-analysis, asymptotics, runtime-analysis, recurrence-relation
---


# Question
Title: Upper (or lower) envelope of some linear functions
Given some single variable linear functions $y\_1=m\_1x+b\_1$, $y\_2=m\_2x+b\_2$, $\ldots$, $y\_n=m\_nx+b\_n$, the upper envelope is the function $f(x)= \max \\{y\_1, \ldots, y\_n\\}$. We know that this function is a convex piecewise linear function characterized by its breakpoints, where the slope of the function changes. I know there exists an algorithm with $O(n \log(n))$ complexity to find the breakpoints. https://www.sciencedirect.com/science/article/pii/0020019089901361

Question: Can the complexity be reduced if $m\_i \geq 0$ for all $i$.

# Answer
Suppose that we add $Mx$ to all your functions. This doesn't change the $x$-coordinate of your breakpoints (because $m\_1 x + b\_1 - m\_2 x - b\_2$ has the same sign as $(m\_1 + M) x + b\_1 - (m\_2 + M) x - b\_2$). Furthermore, for each breakpoint $x$, it just increases the value of the $y$-coordinate by $Mx$. This means that you can recover the original breakpoints, *in linear time*, given the breakpoints for the linear functions $(m\_i + M)x + b\_i$.

Now let $M = \max (-m\_i)$, which can be found in linear time. The functions $(m\_i + M)x + b\_i$ all satisfy your condition. Hence if you could solve your problem in $f(n)$, then you could solve the original problem in $f(n) + O(n)$. Therefore you need not expect a more efficient solution for your special case.
> 2 votes

---
Tags: algorithms, time-complexity, computational-geometry
---


title: Longest Palindrome Brute Force

text:
# Question
Title: Longest Palindrome Brute Force
I'm confused by the running time of the following algorithm. I've been told it's $O(n^3)$, but there are only two loops. How can that be?

```
for(int i = 0; i < s.length(); ++i) {
    for(int j = i; j <= s.length(); ++j) {
        String sub = s.substring(i, j);
            if(isPalindrome(sub) && sub.length() > maxCount) {
                maxCount = sub.length();
                longestP = sub;
            }
    }
}

```

# Answer
> 8 votes
There's a loop hidden inside `isPalindrome()`. Possibly also one inside `substring()` and/or `length()`, depending on how they're implemented.

You can't just count loops. When we say that an algorithm runs in time $O(n^3)$, we mean that it takes "at most roughly" $n^3$ basic steps. You need to check whether the steps of the algorithm really are basic, or whether they also involve iterations through data structures. "Basic" corresponds to something like "taking a fixed number of machine instructions, regardless of the input" but this is an informal analysis, so I'm not going to try to give a formal definition.

There's also the technicality that any algorithm that runs in, say, exactly $n^2$ steps runs in time $O(n^3)$, time $O(n^4)$, time $O(2^{2^n})$ and so on, since the definition of $O(\cdot)$ involves an "at most".

# Answer
> 0 votes
**isPalindrome** function kinda looks like:

```
bool isPalindrome(std::string str){
 int len = str.length();
 int low = 0, high = len - 1;
 while(high > low){
 if(str[low++] != str[high--])
   return false;
 }
  return true;
}

```

So for each i and j steps, the function would run another n times based on the size of input, thus leave us with a time complexity of O(n^3).

---
Tags: algorithm-analysis
---


# Question
Title: What architectural features will allow this microprocessor to access a separate "I/O space"?
I'm studying for my final and don't understand this question. Here is the full question (from Stallings 8th edition):

> Consider a hypothetical microprocessor generating a 16-bit address (e.g., assume the program counter and the address registers are 16 bits wide) and having a 16-bit data bus.
>
> a. What is the maximum memory address space that the processor can access directly if it is connected to a “16-bit memory”?
>
> b. What is the maximum memory address space that the processor can access directly if it is connected to an “8-bit memory”?
>
> **c. What architectural features will allow this microprocessor to access a separate “I/O space”?**
>
> d. If an input and an output instruction can specify an 8-bit I/O port number, how many 8-bit I/O ports can the microprocessor support? How many 16-bit I/O ports? Explain.

If I'm following, the answer to "a" is the processor is generating 2^16 = 64 Kbytes and the bus is 16-bit so the answer it 64 Kbytes.

However, for "b", the answer is 64 Kbytes are being generated but since the bus is only 8-bit, it requires twice as many cycles.

For the answer to "c", I am clueless and I think that carries over into me being clueless on "d". :-\

# Answer
> 1 votes
The CPU uses the same address/data bus to access both the memory space and the I/O space. They are however distinguished by an extra signal that tells whether the address/data is in the memory space or the I/O space. For instance, in x86 this signal is called $M/\overline{IO}$ (pin 28).

# Answer
> 0 votes
(For a) & b), my take is $2^{16}$ of whatever are *addressable units* \- the bus size *not* being an indication (see e.g. Intel 8086↔8088). It does not read *16 address lines/signals*, nor does it mention *address multiplexing*.
Implementations *not* supplying a signal for every architectural address bit are somewhat common: *physical* address space may be smaller (or, historically, larger) than the *architectural* address space.)

c) In the programming model, the pivotal feature is existence of *I/O instructions* mentioned in d). Which does not specify whether there are separate instructions for 8-bit and 16-bit ports.
d) assuming no separate instructions for accessing 8-bit and 16-bit ports, both share "an 8-bit address space".

---
Tags: computer-architecture, operating-systems, cpu
---


# Question
Title: How to solve $T(n)= 4T(\sqrt n) +\log^2n$?
Consider the recurrence $$T(n)= 4T(\sqrt n) + \log^2n. $$ I am not able to solve this recurrence, since it involves a square root. Please help me with the solution.

# Answer
> 8 votes
Let $S(n) = T(2^n)$. Then $$ S(n) = T(2^n) = 4T(2^{n/2}) + n^2 = 4S(n/2) + n^2. $$ You can solve this recurrence using the master theorem, and then use $T(n) = S(\log n)$ to obtain a solution for the original recurrence.

---
Tags: recurrence-relation, master-theorem
---


# Question
Title: Converting connected graph to disconnected graph by removing minimum vertices
How to find the minimum number of vertices that need to be removed from a graph so it makes a disconnected graph?

# Answer
> 2 votes
The minimum number of vertices that have to be removed in order to disconnect the graph is known at the *connectivity* of the graph. Wikipedia outlines an algorithm for finding the connectivity of a graph. More efficient algorithms might exist.

A related problem is the vertex separator problem, in which we want to disconnect two specific vertices by removing the minimal number of vertices.

---
Tags: algorithms, graphs
---


# Question
Title: Finding maximal cardinal independent set given oracle
The problem is given an oracle $O(G, k)$ that would say if graph G contains IS of size k devise an algorithm for finding independent set of max cardinality that makes poly number of calls to the oracle. My attempt has been that first finding the maximal possible size and then try to find the set of that size by removing vertices one at a time. I understand for a given node it either has to be in or not in the set, then I noticed that that there are multiple overlaps between chain of removals and I could devise a DP algorithm of sorts. But I'm just really stuck after that and was wondering if any hint could be given.

# Answer
> 0 votes
Let $O(G)$ be an oracle that returns the maximum cardinality of an independent set in $G$; you can implement it given your oracle using binary search.

Pick an arbitrary vertex $v$, and form a graph $G'$ by removing $v$ and all its neighbors. If $O(G') \< O(G) - 1$ is false, then $v$ doesn't participate in a maximum cardinality independent set, and we try more vertices until we find a vertex that does. If $O(G') = O(G) - 1$, then we put $v$ aside, and continue in the same way with $G'$.

Taking all vertices put aside, we obtain a maximum cardinality independent set of $G$.

---
Tags: algorithms, graphs, np, search-problem
---


# Question
Title: Proving that L is not regular by showing that $\equiv_L$ has infinite index
Proving that L is not regular by showing that $\equiv\_L$ has infinite index.
$\Sigma$ = {a}, L = {$a^{3^n} : n \geq$ 0}
My ideas:
theorem of Myhill-Nerode: L $\in$REG $\Leftrightarrow$ $\equiv\_L$ has finite index
We show: $\equiv\_L$ has infinte equivalence classes.
$a^{3^i}$ $\not\equiv$ $a^{3^{i+k}}$, $k\>0$
-\> equivalence classes: \[a\], \[aaa\], \[$a^3$\]...
Every $a^{3^i}$ is a different equivalence class. Therefore $\equiv\_L$ has an infinite amount of equivalence classes $\rightarrow$ L is not regular. qed.

How to show that the classes are different?

# Answer
Let me prove a stronger claim: every two words over $\\{a\\}$ are inequivalent with respect to your language. What this means is that for every $i \neq j$, there is a word $w \in a^\*$ such that either $a^i w \in L$ and $a^j w \notin L$, or vice versa. Since $w \in a^\*$, in fact $w = a^k$ for some $k$, and so we need to prove the following:

> If $i \neq j$ are natural numbers then there exists a natural number $k$ such that exactly one of $i+k,j+k$ is a power of 3.

Let $a\_i$ be the smallest power of 3 which is at least $i$, and define $a\_j$ similarly. If $a\_i \neq a\_j$, say $a\_i \< a\_j$, then we can take $k = a\_i$. So suppose $a\_i = a\_j = a$. Without loss of generality, $i \< j$, and so $i+a \< j+a$. The next power of 3 after $i+a$ is $3(i+a)$, and after $j+a$ is $3(j+a)$. Let $k = 2i+3a$. Then $i + k$ is a power of 3 by definition, but $j+a \< j + k \< 3(j+a)$ is not a power of 3.
> 2 votes

# Answer
Here is a simpler proof. We will show that for every $\ell$, the equivalence relation $\equiv\_L$ has at least $\ell$ equivalence classes.

Given $\ell$, find $n$ such that $3^{n+1} - 3^n \geq \ell$. Consider the $3^{n+1} - 3^n$ words $a^0,a^1,\ldots,a^{3^{n+1}-1-3^n}$. I claim that they are pairwise inequivalent. Indeed, suppose $0 \leq i \< j \leq 3^{n+1} - 1 - 3^n$. Let $k = 3^{n+1} - j$. Then $$ 3^n + 1 \leq k \leq k + i \< k + j = 3^{n+1}. $$ In particular, $k + i$ is not a power of 3, whereas $k + j$ is a power of 3. Hence $a^i a^k \notin L$ whereas $a^j a^k \in L$, showing that these $3^{n+1} - 3^n \geq \ell$ are pairwise inequivalent. Hence there are at least $\ell$ equivalence classes.
> 1 votes

---
Tags: formal-languages, regular-languages, automata, finite-automata, regular-expressions
---


title: Algorithm for idempotent algebra

text:
# Question
Title: Algorithm for idempotent algebra
A boolean algebra expression can be converted into an idempotent algebra using $$\bar a \equiv 1-a, \qquad a \vee b \equiv a+b -ab, \qquad a \wedge b \equiv a \otimes b$$

where $\otimes$ is the idempotent product (no powers). For example, $$(a+b)\otimes(a-b) = a -ab +ab - b = a-b.$$

The CNF formula

$$\phi = (a\vee b) \\; (b \vee c)(b \vee \bar c)(\bar b \vee \bar c) \\; (a \vee c)(\bar a \vee \bar c)$$

can be converted into what I would call the idempotent expression $$\phi = (a + b - ab)\otimes (b-bc) \otimes (a+c-2ac).$$

This expression expands to give $\phi = ab - abc$. I would like an algorithm that, given a CNF formula as input, outputs the term with the lowest homogeneity. In this example, the oracle would return $ab$. (If there are multiple terms all with minimal homogeneity, the algorithm can return any one of them.)

Question 1: What is the complexity of this task? How high in the polynomial hierarchy is it?

Secondly, given a different idempotent expression $$\phi = ac+ad+bc+bd-abc-abd-2acd-2bcd + 2abcd,$$

I am interested in summing over the terms with equal homogeneity. By letting all variables be $\epsilon$ we get $$\phi = 4\epsilon ^2 - 6\epsilon^3 + 2\epsilon^4.$$ This yields a homogeneity vector of $\[0,0,4,-6,2\]$.

Question 2: What is the complexity of computing the homogeneity vector, given an idempotent expression as input? How high in the polynomial hierarchy is it?

# Answer
> 2 votes
Let us consider the following decision version of your first problem:

> Given a SAT instance, does its multilinear representation have a term of degree at most $d$?

I claim that this is the case iff the SAT instance has a satisfying assignment with at most $d$ ones.

Indeed, suppose first that $m$ is an inclusion-minimal term in the multilinear representation of the instance. Substituting 1 for the variables in $m$ and 0 for the variables outside of $m$, we get 1, that is, that the instance is satisfied. This shows that if the multilinear representation has a term of degree at most $d$, then the instance has a satisfying assignment with at most $d$ ones.

Now suppose that all terms in the multilinear representation have degree more than $d$. If we substitute any assignment with at most $d$ ones, then all monomials equal 0, and so the assignment falsifies the instance.

Therefore the decision version is equivalent to MIN-ONES-SAT, which is the following problem:

> Given a SAT instance, does it have a satisfying assignment with at most $d$ ones?

The problem is in NP (it is easy to count the number of ones in a satisfying assignment), and it is clearly NP-hard (take $d = n$). Hence the problem is NP-complete.

---

Using an NP oracle, we can easily find a monomial with minimal degree, equivalently, a satisfying assignment with the least ones. Just substitute a 0 in one of the variables, and see if it increases the minimum weight of a solution. If so, set this variable to 1, otherwise set it to zero, and continue to the next variable. This answers your first question.

---
Tags: complexity-theory, np-complete, boolean-algebra, oracles
---


# Question
Title: CTL formula for "for every computation it is always possible to return to the initial state"
In the book 'Principles of Model Checking' by Christel Baier and Joost-Pieter Katoen they state that the CTL formula for " for every computation it is always possible to return to the initial state" as 'AGEF start'. I was wondering whether the formula 'AGF start' would also be a valid one ? Is this correct ?

# Answer
$AGF start$ is not a well-formed CTL formula, since in CTL you cannot write GF. Every temporal quantifier must be preceded by a path quantifier.

However, $AGF start$ is a formula in CTL\*, so we can ask your question about CTL\*:

> Is the formula $AGFstart$ equivalent to $AGEFstart$?

The answer to this question is no. The first formula says that in every path, you will visit start infinitely often, while the second one only claims that on every path, you can always find *some* way to get back to start.

Try constructing a system that satisfies one but not the other.

Hint: if $AGFstart$ holds, then $AGEF start$ also holds.
> 1 votes

---
Tags: computation-tree-logic
---


# Question
Title: What is the purpose of a single input, single output, bidirectional shift register?
<sub>(source: edu.au)</sub>
This is the sort of bidirectional shift register, I'm talking about.

I understand why the normal right shift is useful, but when you shift it left, all you're really doing is sending the data input straight to the output. Is there a useful reason for shifting bits in this manner? EDIT- I'm trying to understand how the when shifting to the left, the value int left most register is outputted at the right most end. It makes no sense. Shouldn't the output be what the input is when shifting left?

Thanks!

# Answer
a) if during left shift the output signal immediately followed the input, output changes were no longer *synchronous*. (And the circuit would just act as a "buffer".)
b) `when you shift it left, all you're really doing is sending the data input straight to the output` no:
it shifts the FFlops' data right to left, capturing *Input data* in the rightmost one (the one driving *Output data*, **clocking** *Input data straight to the output* ). All but the latest capture become observable again when you switch to *shifting right* and shift, only.
> 0 votes

---
Tags: computer-architecture, sequential-circuit, shift-register
---


title: LRU vs FIFO page replacement

text:
# Question
Title: LRU vs FIFO page replacement
I am wondering if there is an instance where FIFO results in less page faults than LRU. For example:

```
2,6,5,7...

```

In this string, if I have to complete it by giving 3 additional terms, can I prove FIFO shows less page faults

I have proved how LRU can show less Page faults. But I cannot think of the initial problem statement solution. Any hints would really be great!

# Answer
> 2 votes
For anyone visiting this thread in the future, FIFO can have less page faults in some scenarios.

In this one ( \<2, 6, 5, 7, ..., ..., ...\> ), it can be completed with 2, 8, 6.

The access of 2 means that the least recently used page is 6, but the first page in is still 2.

The access of 8 replaces 2 in FIFO, but 6 in LRU.

The access of 6, therefore, is a hit with FIFO, but a miss with LRU.

---
Tags: algorithms, operating-systems, memory-hierarchy, page-replacement, cache
---


# Question
Title: Given a set of sets, what is the largest common intersection between them?
Given a set of sets: $S = \\{~\\{1, 2, 3\\}, \\{2, 3, 4\\}, \\{1, 3, 4\\}~\\}$, I would like to find the largest common subset of $S$. If $S$ does not have a subset across all elements of $S$, I would like to find the largest common subset across the largest subset of $S$.

For example:

$S = \\{~\\{1, 5, 4\\}, \\{2, 3, 4\\}, \\{1, 3, 4\\}~\\}$ has $\\{4\\}$ in common across all subsets.

$T = \\{~\\{1, 2, 6\\}, \\{2, 3, 4\\}, \\{1, 3, 4\\}~\\}$ has $\\{3, 4\\}$ in common across the subset $\\{T\_1, T\_2\\}$

# Answer
> 0 votes
I understand the problem to be the following:

> Given sets $A\_1,\dots,A\_n$, find the largest $k$ such that there exist $k$ distinct indices $i\_1,\dots,i\_k$ that make $A\_{i\_1} \cap \cdots \cap A\_{i\_k}$ have a non-empty intersection.

This can be solved in $O(nm)$ time, where $m$ denotes the maximum size of any of the $A\_i$. It suffices to find $x$ in $A\_1 \cup \cdots \cup A\_n$ that maximizes $|\\{i : x \in A\_i\\}|$ (i.e., the number of sets $A\_1,\dots,A\_n$ that contain $x$). When you've found this $x$, you can output the corresponding set $\\{i : x \in A\_i\\}$ of indices. You can output the intersection $\cap\_{i : x \in A\_i} A\_i$ too if you want.

Naively, this might appear to take $O(n^2m)$ time. However, the algorithm can be implemented in $O(nm)$ time, by scanning through the elements of the sets, maintaining a hashtable with a counter for each element $x$ that counts the number of sets it is contained in, and incrementing the right counter as you encounter each element.

The correctness follows from the fact that if $A\_{i\_1} \cap \cdots \cap A\_{i\_k}$ has a non-empty intersection, there must be some $x \in A\_1 \cup \cdots \cup A\_n$ that is contained in $A\_{i\_1} \cap \cdots \cap A\_{i\_k}$, and thus the algorithm above will find that combination of indices.

---
Tags: algorithms, sets
---


title: Knapsack with a fixed number of weights

text:
# Question
Title: Knapsack with a fixed number of weights
Consider a special case of the knapsack problem in which all weights are integers, and the number of different weights is fixed. For example, the weight of every item is either 1k or 2k or 4k. There is one unit of each item.

If there are $n$ items, and the number of different weights is $d$, then the problem can be solved in time $O(n^d)$ as follows:

* Define a *configuration* as a specification of how many items of each weight are in the knapsack (for example: "10 items of weight 1k, 19 items of weight 2k, 5 items of weight 4k"). The number of configurations is $O(n^d)$ since there are at most $n+1$ options for each weight.
* Construct all configurations in which the sum of weight is at most the knapsack capacity $C$.
* For each configuration specifying to take $z\_w$ items of weight $w$, take the $z\_w$ highest-valued items of weight $w$.
* Find the configuration leading to the highest total value.

Is there a more efficient algorithm? Particularly, is there a greedy algorithm for this problem?

I tried two greedy algorithms, but they fail already for weights 1 and 2. For example, suppose there are 3 items, with values 100, 99, 51 and weights 2, 1, 1:

* If the capacity is 2, then the greedy algorithm that selects items by their value fails (it selects the 100 while the maximum is 99+51).
* If the capacity is 3, then the greedy algorithm that selects items by their value/weight ratio fails (it selects the 99+51 while the maximum is 100+99).

However, this does not rule out the possibility that another greedy algorithm (sorting by some other criterion) can work. Is there a greedy algorithm for this problem? Alternatively, is there a proof that such an algorithm does not exist?

# Answer
> 3 votes
In your case that the sizes are only 1, 2 or 4, the answer is quite easy:

If the knapsack has an odd size, then you pick the most valuable item of size 1 and add it to the last slot.

If the remaining knapsack has a size that is an odd multiple of two, then you pick the most valuable item of size 2, or the two most valuable items of size 1, whichever is more valuable, and put them to the last slot of size 2.

Now the remaining knapsack has a size that is a multiple of 4. You pick the most valuable item of size 4, or the two most valuable items of size 2, or the four most valuable items of size 1, or the most valuable item of size 2 plus the two most valuable items of size 1.

With other sizes, say sizes 2, 3 and 5, things will be more difficult. However, you can sort the items of each size in descending order, and can solve this using dynamic programming.

I suppose the time will be polynomial for every fixed size of weights, with the polynomial depending on the weights. But you can sort the items of each weight in descending order in O (n log n), and if there are m different weights and the size of the knapsack is K, you find the best solution easily in mW steps.

If the weights and K are large, the number of possible sums of weights may be a lot smaller than K. For example if K = 1 billion and three weights \>= 100 million, there will be less than 167 possible sums of weights \< K.

# Answer
> 1 votes
My comment didn't address your constraint on the number of distinct weights, but since you don't also constrain the number of distinct values, the result is that the number of distinct *ratios* is not constrained. This is likely to be a problem for other kinds of greedy orderings.

Let's call the number of distinct weights in an instance of your problem $d$.

I don't know a way to prove that *no* other possible ordering can work, but here is a strategy that can be used to rule out a particular given ordering. I'll work through this for your greedy-value-descending (GVD) algorithm (even though you already found a counterexample in this case so it doesn't tell you anything new):

The greedy-ratio-descending (GRD) algorithm I described in my comment optimally solves instances of the 0-1 Knapsack problem for which no partial item remains. That means that for some other greedy ordering to be correct, then on any such GRD-solvable problem instance in which all ratios are distinct, it must agree with GRD on the choice of the items to include. (The order doesn't have to be identical -- it is allowed to choose the items to include in a different order.)

Let's start with an arbitrary instance of your problem with some given $d$, which has distinct ratios, too many items to fit completely in the knapsack, all item values at least 3, and which can be solved optimally by GRD, and look for a way to convert this into an instance that has $d'=d+1$ distinct weights and obeys the other constraints (distinct ratios, not all items fit, values $\ge 3$, optimally solvable by GRD), but will confuse GVD. That is, we are designing a function that maps instances to instances. The domain of this function is infinite (e.g., take any instance with distinct ratios and add a "critical" item with weight equal to $C$ minus the sum of the weights of all items "completely" chosen (i.e., with fraction 1) by GRD, and choose the item's value to make its ratio halfway between $v\_i/w\_i$ and $v\_{i+1}/w\_{i+1}$); if we can show that the range is also infinite (e.g., because the function is one-to-one), then we have established that GVD will produce the wrong answer on an infinite number of problem instances that use $d'$ distinct weights.

One possible transformation is: Multiply all values by $4M$, where $M$ is the product of all distinct weights, and multiply the capacity and all weights by 2. Take the last item chosen by GRD, which has ratio $4Mv\_m/2w\_m$, and split it nearly in half: one item with value $2Mv\_m+1$ and weight $w\_m$, and one with value $2Mv\_m-1$ and weight also $w\_m$. (Multiplying numerators by $M$ ensures that all ratios are integral; the slightly different numerators serve to keep all ratios distinct, since all other ratios are $0 \mod 4$.) Finally add a "decoy" item with value $4Mv\_m-3$ and weight $2w\_m$. This construction adds at most one new distinct weight, namely $w\_m$, so $d' \le d+1$.

The (unique optimal) solution produced by GRD on this new instance will correspond to the (unique optimal) solution it produced to the original instance, choosing both "halves" of the critical item and excluding the decoy, for which there is no room left. OTOH, since we required $v\_i \ge 3$ for the input instance, then in particular $v\_m \ge 3$, implying $4v\_m-3 \> 2v\_m+1$, so GVD will consider the higher-valued "decoy" item before either half of the critical item -- so at that time it will pick this item if it has room, necessarily resulting in a suboptimal solution (and if it doesn't have room, then it must be because it has already picked items not picked by GRD, which also leads to a suboptimal solution on account of our assumption that the optimal solution is unique).

This instance mapping is injective: different-size inputs map to different-size outputs, and for two differing inputs of the same size, there is a smallest-ratio item that appears in exactly one of the two inputs, and which leads to an output item that does not appear in the other output.

---
Tags: greedy-algorithms, knapsack-problems
---