...the manager has, that in case there's
some penalty, they're okay also.

They still made a lot of profit.

So the person suggesting this contract
knows that, yeah, there's some tolerance.

And that tolerance is the variable,
well, Karp calls a K.

It just gives it the letter K.

It doesn't give fancy names, meaningful
names to our variables.

It's mathematically, originally
mathematically oriented.

So it's K.

Now, again, while this actually makes
sense in the context of the problem,

we mentioned that the
role of K was to turn a

optimization problem
into a decision problem.

Because the problem is going to ask,
can you create, can you provide a

permutation of your problems
such that when you add

up, when you check, do
they meet their deadlines?

And you add up the
penalties for any internal task

of the end tasks that
did not meet the deadline.

If you add up their penalties,
will their penalties in total be less than

or equal to the, to the manager defined
tolerance threshold of K?

And if so, the manager is still happy.

A lot of profit was made.

It was a good job.

And that's the job sequencing problem.

Now, the way I presented it is 100%
accurate.

There's a slight little twist,
not twist, a slight little different

presentation, slight, in that the way the
inputs work when you read Karp's paper,

everything I said is true.

But that the information, the way you
figure out the deadlines...

Well, he does talk about
it, but the bottom line

is, each task takes a
certain amount of time.

So, the point is, you know what day you
start the task, you know what day you end

the task, and you
subtract the two, then you

get the number of days,
the way I presented it.

I believe that in Karp's definition,
you actually say how many days,

when's the start date, how
many days, and then you

know the deadline,
anyway, or it's given to you.

The point is, the number of days is also
given to you.

But whether it's explicitly given to you,
or in my case, it's easy, just you know

when you're starting, and the deadline,
and you know when it's ending,

so that's the start and end date.

Either way, you have the same information.

The bottom line is that these
three problems are the only

three problems in the Karp
21 that involve permutations.

Okay?

So that's a connection between problems 9,
10, and 11.

Okay, now, the next two bunches of
problems, two iterations full,

so let me just show you, 12, 20,
and 21, and 4, 6, 14, and 18.

So, it's all going to dance
around the mathematical

notion of a partition, which
we'll talk about in a second.

We actually talked about
it at the end of a lecture two

weeks ago on exhaustive
searches, size of the search spaces.

12, and 20, and 21 are very clearly a
partition.

4, 6, 14, and 18 sort of dance around it,
in order to loosen it, and as such,

instead of calling it a partition,
I call it a packing.

But the fact is that they are dovetailing
partitions.

There is a similarity.

I keep them separate because the other
four sort of loosen it.

Whereas here, partition is strictly the
mathematical definition of a partition.

So let's do the mathematical definition of
a partition, which is problems 12,

20, and 21.

Let's talk about them.

And then we'll go through the loosened
version, which I call packing.

There is a notion of mathematical packing
in geometry, advanced geometry.

We're not talking about that.

We're talking about actual packing a
suitcase, okay?

I'm talking colloquially at that point.

Partition is mathematical, strictly
defined.

Packing has a strictly defined definition,
but that's not us.

I meant suitcase packing, all right?

Like the problem knapsack is going to be.

And we actually once talked about it
earlier, last class.

All right, here it goes.

What's the definition of a partition?

So the definition of a partition is you
have a bunch of elements.

And in the original edition, it's a
partition of a set.

And by default, we know
that sets are unordered,

which means you cannot
have duplicate elements.

That's going to be
important because the

definition of a partition
sort of expects that.

So we're dealing with an unordered set.

And you temporarily assign them numbers,
you know, numbers in terms of item one,

two, and three, just so we could call the
item.

You could call it book, dish, you know,
CD, and fork also.

But anyway, we'll call them elements,
you know, whatever, different elements.

Okay, so you have a partition.

Now, what's the point?

You want to divide up all the elements of
your original set into its own group of

subsets, such that the following holds
true.

Now, at this point, there is a,
as I mentioned in the, when we originally

defined it and counted how many there are,
how many partitions there are,

and related to the bell
number, the set of all, the

number of all possible
partitions over the set of size n.

There is a slight distinction in that,
did you know ahead of time how many

groupings, how many sub-sets are you going
to put the elements into?

If you knew ahead of time or you were
told, I want you to divide the elements,

partition the elements of a set,
into K different subsets, such that,

and we'll get to the restrictions in a
second, the constraints in a second,

but the point is that if you were told
ahead of time, so we throw in the K as

part of the name, and we call the K
partition.

If I were to give you all these elements
and say, please do me a favor,

put the, group them together in any manner
and tell me afterwards how you did it,

or give me the inventories afterwards,
then I left it up to you to decide when

you're, when you're putting the elements
away into their subgroups, subsets,

you make the decision at the end,
oh, by the way, I did 17 subsets.

Again, again, we'll do the constraints and
you had to follow the rules.

But the point is, did I, did I tell you,
you're, you're doing me a favor,

and you're putting away all these elements
into these groups, these bags,

and you're, you're packing.

Well, that's, that's where the word comes,
why I relate to it.

It's sort of, you're packing my items for
me.

Anyway, did I tell you, put them into K?

Or at the end, you told me, by the way,
there were K bags, K equals 17.

So, if you, if you told me, and I didn't
tell you, then that's called just partition.

If I told you, then we say it's a K
partition.

Because I told you, you had how many bags
you had to use ahead of time.

Okay, and that's what I say on line 109.

If K is known ahead of time, then this is
actually called a K partition.

Otherwise, it's called a partition.

All right, that's just naming.

It doesn't really change much.

Here are the constraints.

Number one, each, the sub, the groups are
S sub i.

The original set is S, and the subsets are
S sub i.

And the union of S sub i is going to be
the original set.

Because all these together, you only,
okay, well, let's go through it.

You can't have an empty bag.

That's, that's, that's a rule.

Don't tell me they're 18 subsets,
18 bags that you put my elements in.

Oh, by the way, one of the bags is empty.

Well, then you have 17.

So just for simplicity, we say,
in line 112, that, that it's a fancy way.

The empty set is a proper subset.

But the point is, it's not equal.

So anyway, the bottom line is S sub i
cannot be empty.

And finally, clearly, S sub i can't have
elements that are not in the original set.

You can't throw in your laundry in it
also, unless we agree ahead of time.

Right?

You're packing my items up.

So, S sub i has to be a subset of S.

You can't throw in elements that are not
part of S.

And don't waste bags and tell me that you
have 18 bags, 18 bags in my partition,

you know, 18 boxes, load them,
when you know one of them is empty.

Okay?

That's lines 112 and 113.

Okay.

Number 114, what's generally called
mutually exclusive.

Fancy name, mutually exclusive comes from
discrete math.

The point, though, is that you can only
have this, you can only make such a

constraint on line 14, if the set is
unordered, or rather, there are no duplicates.

The order isn't as much.

It's just that unordered guarantees no
duplicates.

But if it's ordered, you have to guarantee
me there are no duplicates.

Why?

Because on line 114, it says that when
you're done putting these elements into

these subsets, into these bags,
and you write an inventory, right?

I don't want to go sift through all these
items.

They're big boxes.

And you sealed the boxes.

And now I'm putting them
in my truck, or my rental

truck, and I'm taking
it to where I'm going.

Right?

So I don't want to start ripping it open
and checking who's in there.

So you wrote an inventory, whatever group
CD, music, and what movie, and what color

shirt, and one can of tuna, however you
did it.

Right?

You're going to write an inventory.

So the point though is
that you can't have two

bags, two inventories that
have a common element.

Now, why can't you?

There's nothing wrong.

The answer is because they're assuming
there are no duplicates.

Now they don't say that, but that's
obviously on line 114 what it implies.

So that's why I believe that the
definition was always unordered,

because unordered guarantees no
duplicates.

However you want to say it, that it's
ordered but no duplicates, or unordered,

in which case it's automatically no
duplicates, line 114 only makes sense that

no subset has anything in common with any
other subset.

So that means no duplicates.

Anyway, that's line 114, no duplicates.

Line 112 is that no subset is
empty, and no bag is empty,

and you didn't put in
items that are not in the set.

That's 112.

Line 114 is that there are no
duplicates between the bags

that you say you're done,
that comprise the partition.

And finally, no element is left behind.

Every element was put into a subset.

So the union of your subsets is S.

Okay, so that's the mathematical
definition of a partition.

Okay, so now we have the following three
problems, 12, 20, and 21, where the

underlying mathematical structure is a
partition.

So chromatic number.

Chromatic number is a really old
mathematical problem.

Many, many books and theorems have been
published on this.

There are some limited cases of chromatic
number that I believe are in P,

but that actually are in P. The general
chromatic number problem is not, though.

All right, chromatic means color,
like colors of paint.

That's literally what they were talking
about.

So let's imagine you have your nodes,
right?

Like let's imagine they're circles, and
lines are the edges connecting these circles.

And you're a painter, and I hire you to
paint these nodes.

Such that a node, and its adjacent nodes,
meaning there's an edge between them,

do not have the same color.

You actually need different colors on an
edge from one node to the other node.

And the question is, how
many colors, or minimum

amount of colors, but that's
an optimization problem.

So CARP is going to have a parameter and
say, can you do this within K colors?

So someone told you how many colors.

And then the question
is, you're only allowed 17

paints, and you have a
thousand nodes to paint.

And the question is,
can you paint it such that

no node is the same
color as the node next to it?

In what sense?

Only if, meaning if there's an edge
between them, okay?

If you draw the graph, and there are two
nodes looking next to each other,

appear next to each
other in the same color,

that doesn't necessarily
cause a problem.

The only problem would be if there's an
edge between the two nodes, and then the

two nodes of that edge have the same
color.

You need the nodes of the edges locally.

Now, it's one edge at a time.

Does the two nodes have a different color?

Okay.

Now, the anecdote that I'd
like to say is an interview I heard

once, a number of years ago,
an interview of Taylor Swift.

So, she was building a ranch, I think in
Texas somewhere.

And she said that... So, she described
a little bit of her experience in design.

And she was inspired, she didn't say she
was inspired by a chromatic number,

but she was, in the following sense.

One of the design that she thought would
be really cool is that all the cabinets in

her kitchen, the knobs have to have
kitchen themes.

So, you have to...

One knob, the face
plate will be a fork, and

you turn that or pull
that to open the cabinet.

Another knob will have a spoon.

Another knob will have a knife,
right?

And she wanted to have different...

And the key is that if a cabinet had two
doors, here's the chromatic number issue.

So, like an edge, two nodes connected to
each other.

If a cabinet had two doors, the two knobs
had to be different.

You couldn't put knife, spoon,
or fork...

Knife spoons, okay.

You couldn't do spoon, spoon, or fork,
fork.

You could do fork, spoon, knife,
fork, etc.

So, that was very similar.

That is the essence of the chromatic
number problem.

But Taylor Swift didn't know she was a
mathematician.

Anyway, so, chromatic number.

And the question is, can you...

Can you paint this graph?

Which you're painting only the nodes of
the graph.

Can you paint this graph with K paints,
K colored paints?

Okay.

Now, why is that a partition?

Because, in essence, if you think about
it, let's say whatever...

However you painted this graph,
take one color at a time, and then could

take the vertices that were painted with
that color.

So, in essence, what you have is a
partition.

So many of the elements were painted with
yellow.

So many of the elements were painted with
blue, etc., etc., etc., etc.

Right?

Now, it's true there are a little extra
constraints.

But in essence, what you're generating is
partitions.

If you were to... a K partition.

If you were to generate all the K
partitions, right?

And we'll call the paints, paint one
through K.

All right?

Or if you want to do zero through K minus
one in the C-based programming.

Anyway, whatever it is, however you want
to do it.

Let's say one to K, right?

So that the index one is going to be a
linked list or some sort of storage of the.

..

The point is you're generating a
partition.

And whatever you... Color
number one is subset number one.

Color number two is subset number two.

So you can't have duplicates.

You can't paint a node with
two... The elements are the nodes.

You can't paint a node with two colors.

You have to paint every color.

And you can't use a paint except with the
K.

Now, the only
thing extra... Right?

And you had to paint everybody.

So that is a partition.

But there's an extra constraint.

After you do that, not every such
partition is valid.

Because now you've got to check the graph
data to make sure that for every edge,

the color paint used for each of the nodes
are different.

But in essence, you are generating
every...

If you... Again, if you didn't have a
non-deterministic machine, then you could.

..

It'll take a long time.

There are lots of these.

More than exponential, at least...

Factorial, at least.

Whatever it is.

Again, the bell number.

More variation thereof.

The point... Though,
whatever it is, it is deterministic.

You could generate all partitions.

Try one by one.

And find one
that... K partitions.

Not just any partition.

Generate all K partitions.

And see if it matches the constraint that
no edge has the same color on the nodes.

Okay.

So that's problem 12.

Problem 20 is a K partition.

It's by definition K
partition with a very

simple little extra check
that you have to do.

Constraint that you have to do.

The only thing is that the partition problem
that CARP defined is when K equals 2.

Obviously, the partition problem is a very
important problem in many applications,

such as scheduling of parallel processing,
etc.

Lots of... What's
called load balancing.

And so, the general K partition is a very
important problem.

But just technically, so you remember for
any exam, CARP partition problem,

there were only two subsets.

That was the question.

And the idea here is that your items are
weights or values.

Imagine dollar values, right?

And you have antiques.

And you... Let's say you and
your partner own an antique store.

And now you want to sell the store.

You both want to go into different
ventures.

You're moving to different states.

You're both retiring, whatever the story
is.

And you want to sell off the assets.

Okay.

So, each of you own 50%.

So, the partition problem says...

Where the...

Let's assume you all agreed upon how much
each item is worth.

So, now you have a bunch of numbers.

And the question is, can you put each of
these numbers into different...

Into two different groups, such that the
sum of the values, the weights...

In each group, when you sum them up,
the tally within group number one.

And the tally within group number two.

Technically subset one and subset two.

They... The total sum within
are equal to each other.

Because that's a perfect partition.

And that's helpful for division of assets.

So, that's the question.

Can you do it?

Okay.

Can you divide a set of weights into two
subsets, into two groups...

That satisfy the partition definition?

Such that when you add up all the weights
in group number one...

And then separately add up the weights in
group number two...

The two total values equal the same total
weight.

If you can, then you have solved the
partition problem.

If not, then you say no.

All right.

Just because you give
a set of weights doesn't

mean you'll always
have a perfect partition.

That's why I kept telling
you that non-deterministic

programming doesn't
always get you the answer.

It's subject to Geigo.

Garbage in, garbage out.

If you give me...

If you, the programmer, give the
non-deterministic computer data that

doesn't have a partition, it's not going
to make one.

They'll say sorry, not possible,
or whatever they'll say.

Anyway, so that's the case, and that's the
partition problem.

So that is a partition.

It's just that it happens to be limited to
k equal to two.

So technically, it's a two partition.

Okay, the last one for this group is
called max cut.

And max cut is a graph problem.

So let's imagine...

Let's imagine you're responsible for a
network.

And you lay many cables between Manhattan
and Queens, let's say.

Okay, now there are cables within
Manhattan.

There are cables within Queens.

Let's imagine you lay the cables between
Manhattan and Queens.

All right?

Now, most network companies will put in
redundancy.

Which means that your data is actually
going across more than...

Not that you necessarily, let me rephrase
that.

Not that your data is going across more
than one cable.

But there's more than one cable that could
send you the data you want.

In other words, it's not that Manhattan
was divided up into sectors.

And one cable from Queens goes to sector
number one.

A different cable goes to sector number
two.

You have to have
extra cables in case you

need maintenance, in
case something happens.

You don't want your customers not to have
the communication.

So they have to put it with extra...
In fact, in general, you have to...

I'm just explaining.

But Max Cutts is a little...
We'll discuss in a second.

But that's the basic idea.

That each cable...

That you're probably going to have a number
of cables that go to sector number one.

A number of cables go to sector number
two.

Anyway, the bottom line is there are also
cables within Manhattan.

There are also cables within Queens.

But that's not the issue or concern by Max
Cutts.

Max Cutts only interested
in the cables between

two groups, not the
cables within two groups.

In graph theory, that designation is
called bipartite.

Bipartite is partitioned.

Bi means two.

So in some sense,
you have... It's a spin-off.

And that's probably why they're near each
other.

There's a clear spin-off of Max Cutts,
a graph problem, and Partition,

a numerical problem.

Anyway, so you have a weighted graph.

You have a graph.

The nodes are the customers or computer
centers.

And the edges are your cables.

And the numbers, perhaps,
in profiling the network,

the cable's numbers may
be the load, the typical load.

How much data in gigabytes are traveling
through?

Because the higher the number,
the more important that cable is.

Right?

Certain cables, certain sectors are going
to have more traffic than other sectors,

right?

You know, that's where this whole new,
what they call congestion pricing,

came about below 60-something streets or
something in Manhattan.

Right?

Automatically, your car gets an extra tax,
an extra toll.

They probably, off
record, they probably did

that because there were
too many complaints.

They wanted to put the
Queensborough Bridge

with a toll, but it
caused too much traffic.

So the city and state city who
thought they were losing money

because people would go
a little extra out of their way.

Right?

It was self-fulfilling prophecy,
as they say.

The point is that the fact
that the Queensborough

Bridge was free
doesn't have a toll.

More people were going to avoid other
bridges and come there, which then caused

extra congestion on the other side of that
bridge.

So in order to balance
the act, what they

did was they created
this congestion pricing.

The toll is free.

Oh, by the way, they
also did it because they

didn't want to slow down
the traffic on the bridge.

Because if they had a toll booth or something
like that, it would slow things down.

Anyway, whatever it is.

So they got their money
back by, instead of taxing

the bridge, which is free,
as soon as you take one...

The car goes one foot into Manhattan,
since it's below 60th Street, boom,

you have to pay $9 tax.

So it's like a toll.

Anyway, so my point, though, is that the
max cut, which let's say in our example,

between Manhattan and Queens, within
Manhattan and within Queens, I'm sure

there are cables, and the graph has those
cables, but we're not concerned.

And each cable has a number associated.

And generally, in most applications of max
cut, that node is the amount of traffic.

Now, you're profiling
your network, and you want

to understand the
vulnerability of your cables.

So, in essence, the problem would be, the
question is, how many cables do you cut?

How many cables, if you were
to cut... Well, okay, that's true.

But in my example, you've already decided
the nodes, because I gave you a location.

In the max cut problem, you're dealing
with...

You're trying to redesign your network.

So the example of Manhattan and Queens
stops here.

See, in my case of Manhattan
and Queens, somebody

told you, who are the
nodes in subset number one?

Who are the nodes in subset number two?

In CARP's problem, you have a big network,
all in one major region.

No islands, Manhattan, no island Queens.

Just you have a bunch of nodes in one big
region.

And now the question is, which, you know,
which two subsets are most vulnerable?

If you were to partition the nodes into
two subsets, into a real partition,

a two partition.

If you were to do a two partition of all
the nodes in this region into two subsets,

okay, fine.

But now comes the constraint, how the
vulnerability is defined by the total sum

of the loads of the weights of the cables
between subset one and subset two.

Because if you were
to cut, literally, and

here, there is a
mathematical notion of a cut.

Here, it literally means somebody cut the
cables.

If you were to cut all the cables between
this particular subset one group and this

subset two group, the sum
of those traffic is the most

as compared to any other
two subsets in your region.

And then that tells you, in terms of
network profiling, what's the most

vulnerable section, where
now you'll know you better

put in these redundancy
cables to protect yourself.

Okay, so just to summarize again,
max cut.

You have a weighted graph.

In most applications, the weights are the
traffic, the load, the traffic.

And the higher number means it's much
busier.

The edges are usually wires, cables,
communications.

And the nodes are sectors, points in your
grid.

Not a square grid, but in your graph grid.

And the question is, how figuring out to
partition, a two partition, divide all the

nodes in your graph into two subsets,
such that, you know, on lines 109 to 115

above, you meet the official definition of
a subset, of a partition rather,

such that, there are many such partitions,
such that, once you pick a partition to

consider, if you were to consider the
cables between the subsets, but not the

cables within the subsets, inter,
between, but not intra, within.

So, and you sum up those loads,
those weights.

And you want to do that amongst all
possible two partitions of your nodes.

So, which two subsets have the biggest max
cut?

Have the largest sum of the cables between
those two groups?

Okay?

And that's called max cut.

So, clearly, the chromatic number,
clearly partition has the word in the

name, and max cut are all partition-related
problems with a little extra.

Chromatic number has a
constraint that the edges, the

two colors of the adjacent
nodes are different colors.

In partition, you're summing up the
weights of the group.

In max cut, you're summing
up the weights between

the group, of the edges
between the group.

Anyway, and that's the partition problem.

Partition number 20, the two partition,
you want that the total sums are equal.

In max cut, you want to optimize and say,
who's the biggest?

So, that's a... max cut is a hard... it's
called a hard problem.

Now, one more second.

I have to double check.

That's funny.

No, one second.

One second.

No, no.

I have to check.

That line 129 bothers me.

Give me one second.

Let me see something here.

That's the wrong file.

Something's funny.

If I can't resolve this very quickly,
I'll edit that line in the notes.

The way it's worded bothers me.

For partition, it's trivial.

The verification of max cut may not be
trivial.

Give me one second.

Let me find the page.

Give me two seconds.

I'm looking up CARP.

You could as well look it up on pages... I
think it's page 97.

Oh!

Okay.

That's what I thought.

Okay.

So, there's a little thing missing here.

What's missing here is... Well, it is
trivial, but not for the reasons we said here.

Give me one second.

I want to know where I should put the
wording.

One second.

One second.

Okay.

I'll reword 129.30.

I just want this part to be correct.

Okay.

Now, right.

The issue is... There was
a sentence missing here.

This would be an optimization problem
whose verification is not trivial.

So, CARP modifies this problem with a
tolerance parameter, W.

That's what he uses for...
This time he uses big W.

And asks...

Can you find... Can one find a max
cut whose sum of the cut... Right?

The cables between them... Is greater
or equal to our threshold parameter, W.

That's the point.

So, he changes it to a decision problem.

Now, a decision problem.

Okay.

So, verification is trivial.

Not the sum.

The one sum.

Well, it is the sum.

Is, not are.

It's not equal.

Is the sum of weights of the cut cables,
cut edges.

I put in cables because it's easier to
relate.

The weights of the cut edges, at least W.

At least W.

Right?

So, you add it up.

Alright.

Now...

So, these... All of these
problems... All of these problems...

All three of these problems...

Involve partitioning.

Plus some other constraint.

Plus a last local constraint.

The constraint.

Uh...

Chromatic...

Uh... The constraint... Okay.

You know what?

Ouch.

No.

That was not smart.

All of...

These three problems...

Involve... Again, a K partition.

Last two... With K equal to two.

Um... But... also, And
then, Plus... One other...

Local... Constraint.

So, we'll see what the constraints are.

Let's see what all the constraints are.

To summarize it better.

So, let's say, chromatic,
the constraint is, do

the edges have two
differently painted vertices?

Two differently painted vertices,
right?

An edge is made of two vertices,
and you need them with different paints.

That's chromatic.

Partition, which is really a
two-partition, and that's how it's defined.

Partition, do the sums of the weights of
each group, which is a subset technically,

because it's a partition, equal each
other.

And in the case of MaxCut, does the sum of
the edges between the groups, again,

subsets, of nodes, to the edges,
the sum of the edges, of the edge weights.

So, it's between the groups of
the nodes, meet the maximum

criteria, the threshold
criteria, the threshold provided.

All right.

So, that's the story, and the verification
is straightforward.

Right?

The verification is easy, in all these
cases.

All right.

So, that's problems 12, 20, and 21.

Good.

All right.

Now comes... they are related to
partition, but ignore that for a fact.

Ignore that for now.

Ignore the fact that they're related to
partition.

Let me give you the story that it
involves, because you'll have an easier

time to understand what the problems are
trying to say.

All right.

Here's the story.

Ignore what I wrote for a second.

And then you'll understand why 4, 6,
and 14 is for sure similar to each other.

And then also why through
knapsack there, which I've

given a little explanation,
but ignore that for a second.

All right.

So, here's the story.

I'm a manager of a warehouse that sells...
our company sells hardware.

Let's say not computer hardware.

Let's say construction hardware.

So, we manufacture hammers.

We manufacture screwdrivers.

We manufacture saws.

We manufacture lots of different tools.

All right.

And once a year in Las Vegas,
I only picked that because

they have an amazing conference
center, convention center.

And in fact, many, many industries
congregate there to have their show,

to have their trade show.

I actually went to a computer trade show a
few years in a row in Las Vegas.

Anyway.

So, it was really, really good conference.

And there were talks and tutorials.

And really all the big computer science
players were there.

And zillions of applications.

Very interesting.

Anyway, whatever it is.

So, that's the story.

I'm the manager of a
warehouse whose inventory

is for a company that
manufactures hardware.

Construction hardware tools.

Good.

And I tell the staff, my staff,
the workers in the warehouse.

I got to go home early today.

But tomorrow, we're going to have to pack
up tools and load the truck.

Because we're taking trucks down to Las
Vegas.

Or maybe I'll tell them we're flying to
Las Vegas.

But we have movers that are going to move
the tools to the trade show.

Right?

And at this trade show, people don't
actually take the tool itself.

The trade show is usually high-level
purchases.

People don't show up and say, go to
Microsoft.

Okay.

Buy one, you know, one license.

Or one box of this.

Or one wire.

They come there and say, how much is,
give me a quote for 10,000 of these items.

It's really meant for display.

Anyway.

So, what happened?

So, these adventurous workers of mine said
to themselves, hey, Las Vegas,

that's a good, you know, nice little
vacation.

It'll be fun.

Right?

So, they said, you know what?

Let's pack it up all now.

Because then we get an extra free day.

We'll work a little harder today.

We'll pack everything up now.

And I don't know this.

They say, we'll pack it up now.

And then we can leave first thing in the
morning.

And everyone says, hey, good idea.

And they pack up the entire warehouse.

Now, I come back the next morning.

Now comes the different versions.

But basically, the idea
is, I never intended that

we should take all the
items in the warehouse.

You see, they misunderstood the last point
I said.

Which is, these trade shows don't sell the
actual items.

I mean, at the last day they will.

Because nobody wants to pay shipping back
home.

So they don't mind
making a sale of the

individual items the
very last hour of the show.

Or sometimes you have to sit there and
wait after the show.

Sometimes, which is really fun.

Because sometimes they just give it away.

They simply, it's not worth their money to
ship it back.

It really isn't for a lot of these cases.

But whatever it is, the point is,
the manager, I never intended that my

workers should pack up the entire
warehouse.

Okay.

So I only want, I wanted them to pack,
but I wanted them to pack judiciously.

With some wisdom.

So now comes the different problems,
based on what did I really want,

what was I intending.

I didn't tell them this, because I didn't
think they would pack overnight.

I thought we would pack today.

They packed everything up all overnight.

Now, all the boxes are sealed.

And they wrote these inventories.

What's in the box?

Because we don't want to rip open boxes.

That's a pain.

That's a waste of time, waste of labor,
waste of everything.

So, and we're going to assume that they
were very accurate.

And the inventories say exactly what's in
there.

All right.

So now comes the question.

So, one second.

Let me move this over.

I just realized the pagination is slightly
off.

All right.

So, let's take problem number four.

There are already packed boxes.

You see, in problems 4, 6, and 14, in column
D, I start the story the same exact way.

Right?

If you look at lines 138, 140,
and 142, after the name of the three

different problems, the numbers 4,
6, 14, in column A, set packing,

set covering, or set cover, set coverings,
and exact cover in column B.

Packing, packing, packing.

That's the commonality in C.

And now the line in column D.

It's the exact same line.

Already packed boxes.

They already packed it.

The question is to choose which boxes to
take.

All right.

All right.

So, in the case of set packing, the manager
says, all right, I'll tell you what to do.

Now, generally also, by the way,
okay, yeah, yeah, okay, fine.

CARP may have a parameter here,
but ignore that for now.

So, in set packing, now on line 139,
all the workers packed all the boxes.

And the manager says to them, pick some of
those boxes.

The truck will not allow.

The movers that I hired
with their 20-wheeler or

whatever it is, will not
take all these boxes.

It's too much weight.

The tools weigh a lot.

They're not taking all these boxes,
right?

Find, to me, a set of these boxes.

Now, it's not all the original boxes,
but some of those boxes.

Such that, basically, I want to maximize
the amount of elements.

So, the trucker is
going to tell me, you

can't have more than
20 boxes in set packing.

Right?

You can't have more than a certain number
of boxes.

But I want to maximize my trade show.

So, and since it's all meant to be,
since it's all meant to be a display

anyway in Las Vegas, so I might as well
bring that as many, the boxes,

20 boxes with as many different tools as
possible.

Because then I can take orders and
demonstrate more and more tools.

And that's the goal in set packing.

No two boxes...

Okay.

Which box to take?

L boxes max.

Okay?

So, there's a parameter here.

The CARP uses the letter L for some
reason.

L boxes max.

You can't pack, you can't put on the truck,
I can't take with me more than L boxes.

Now comes the constraint.

No two boxes taken may have similar
elements.

That is the issue here on line 114.

So, it's not exactly a partition.

Because I may not be taking all elements,
line 115.

But instead of demanding let's get one of
each element, I rather save the weight.

And say, take, read the inventories on
these boxes.

And take L 20 boxes.

Such that no box has anything in common
with any other box.

Okay?

So, that is set packing.

Set covering.

So, the story in set covering sounds the
exact same story.

Right?

But here, and he uses the letter K for
some reason.

K boxes max.

All right.

So, here, already packed boxes.

The question is to choose which boxes to
take.

The criteria is, I want every item.

So, in essence, I'm willing to ignore line
114.

I'm ignoring line 114.

Because I know that there's going to be
overlap.

You know, box one doesn't only have
hammers.

And box two doesn't, what my workers did.

And box two doesn't only have saws.

And box three doesn't only have
screwdrivers.

Because we have lots of tools.

And they packed everything.

So, there will be a hammer here,
a hammer there, a hammer there.

But I want to make sure because of my
display in the convention hall.

Right?

I want to make sure that one of every item
we manufacture I can put on display.

So, I'm ignoring duplication, which will
cost me extra money.

Because the mover is going to say how much
weight.

You know, and if had less weight,
it would cost less moving.

But we're ignoring that.

But instead, we want in favor of line 115.

So, set packing favored line 114 over line
115.

And set cover favored 115 over 114.

In other words... In
other words... Okay?

So, favored line...
Oh, so it's not 106.

Line 114... Oh, well... Okay.

Maybe I should ignore that.

Line 114 over line 115.

And this favored line 115.

And this favored line 115 that you have
every element over 114, which said...

Which said what?

Which said... Give me a second.

Which said that uniqueness as opposed to
duplication.

So, this is line 114.

This is line 115.

This is line 115.

Okay.

Good.

Now, comes exact cover and the manager
says, I want both worlds.

I want you to retroactively actually get
me a partition.

Okay?

But... Here's the problem.

The problem is... In problem
number 14, exact cover...

No, no.

So, here there's no constraint.

That's the problem.

I want you to find an actual partition.

So, I've already packed boxes.

The question is which boxes to take.

I want you to choose
the boxes so that there's

no duplication and
every item is present.

I want everything.

I want both.

I want both.

I want both.

I want both.

An actual partition.

Now, the only one thing here is I say L.

I'm trying to remember because I don't
think CARP actually tells you how many.

One second.

Give me one second, please.

Ah!

Okay.

No.

No, it's not true.

Give me one second.

Yeah.

There is an implicit parameter here.

The problem is he doesn't say...

That's why it's a little confusing.

First of all, it's not L.

It's H this time.

I'll put this in parentheses because he
doesn't word it that it's a parameter.

He just may be using H generically.

That's a little unclear.

Anyway, the bottom line, it's a little bit
unclear in CARP's.

I don't know how much wording whether this
H is actually a parameter.

But the bottom line is I want
you to pick... It's already packed.

And I want you to pick
boxes such that there's

no duplication and
every item is present.

So, it's basically an actual...

This favors lines both.

Basically reconstructing an actual
partition from

the packed boxes.

Okay?

So, I want both.

All right.

So, that's 4, 6, and 14.

Now, knapsack is packing.

The only thing is you haven't packed yet.

So, that's the difference.

But it is packing.

Remember?

Knapsack.

I lay out all the items that I potentially
want to take.

I'm mindful that the airlines tell me I
can't have more than 50, 70, 32,

whatever the number of pounds is.

I can't have my suitcase including the
suitcase way more than that.

I pre-weight.

I put on the scale all the items so I know
how much every item is.

And I would like to take, although it's
not formulated this way, but in a

practical sense, it's helpful to you to
take, if you don't mind carrying a little

more, but it's helpful to you to take as
many items as you can.

You're flying overseas, and it'll be
easier to you if you have an extra shirt,

an extra book, an extra can of food,
however you pack.

You know, you could be
adventurous and maybe you pack

nothing, you know, and buy
everything there or just wing it.

Then some people enjoy doing that.

But if you want to take a
more traditional approach,

it's helpful to you to have
more extra with you, right?

Just in case.

Why not?

Assuming you don't mind carrying your
suitcase, which now weighs a few more pounds.

But you can't have... you don't want a
penalty, which is that the airlines will

charge you extra if you're over the weight
B.

Alright?

Anyway, note, the commonality
here is the application is

similar, but not that the
brute force approach is similar.

Okay.

The point is that the definition of
knapsack involves packing.

But the solving of knapsack isn't actually
a partition.

You see, set packing,
set covering, and stack

cover play around with
the notion of a partition.

In knapsack, it's not really a partition
because... well, it's a little bit,

but not really, because you're not taking
all the elements.

Instead of packing,
set covering, and stack

cover, somebody actually
packed all the elements.

And now you realize you can't take all the
boxes.

So it's a more broader version of a
partition.

But in knapsack, you
never planned to take

all the items, and now
you're trying to pack.

Anyway, I wanted to remind you on lines
146 to 149, just because a problem is

defined a certain way does not mean that
that is the way to solve it.

Okay?

That doesn't mean that that is the way to
solve it.

For example, consider problems 7 and 8,
right?

And we mentioned there, we mentioned that
although the definition of the feedback

sets involve cycles,
the solution to CARP's

problem does not involve
generating a cycle, right?

Because you delete your sets.

You delete your sets.

I think it's line 42, 43.

Anyway, you delete the sets, and then
you're just checking if there's no cycle.

And the verification is in P. But you
don't generate the actual cycles.

Oh, I say that.

Both of these are defined
in terms of all cycles,

but the exhaustive search
actually does not do that.

Okay.

Finally, related towards the end of class,
packing is different than partition in

that a fundamental rule in partition is
that no one is left behind.

But in packing can and often do.

Right?

So we said above line 115 is that every
element is taken.

Well, it's even more than that.

You see here, they're duplicate elements.

Okay.

Packing is different than partition.

First of all, is that a, is that a, there
can be duplicates in the original set.

100% there'll be duplicates.

And b, partition, no element can be left
behind in a partition.

But when you pack, you often do.

All right.

That's a little better.

All right.

So that's the story.

Now, I mentioned though, the following,
which is interesting.

The actual partition, again, knapsack
isn't really a partition problem.

But you could have a similar grouping.

Let me just finish with this comment.

We'll stop here.

Because I don't want to have to repeat the
problems.

4, 6, and 14 are variations or loosenings
of a partition.

18 is not a partition, but it is packing.

But problem 20 is a partition.

So 4, 6, 14, and 20 all deal with the
mathematical notion of a partition.

It's just that 4 and 6 loosen it,
and 14 is technically an actual partition.

But you leave behind the duplicates, and
you have more elements such as duplicates.

So it's a little different than normal
partition.

And then 18, technically, is not a
partition.

Because you have to leave elements behind.

All right?

The original elements.

Because not all the original elements are
packed in knapsack.

It can be left out.

Okay.

Okay, good.

And true partitions.

All right, it's the end of class.

If you didn't have a
chance, please text the

word present, and I'll
send you these notes.

Well, you have the notes.

At the end, at the very
end, when we're finished

in two weeks, I'll send
the updated version.

Okay?

I think it'll be simpler that way.

Otherwise, we'll have way too many
versions flying around.

All right.

That's the end of class.

So if you could text the word present,
and we will continue on Monday.

Again, we're using the same set of notes
probably for one more week.

Possibly two or three lectures.

Depends how it goes.

I'm not purposely trying to rush it.

But anyway, we'll see how it goes.

All right.

Wow.

Hmm.

This weather is throwing me for a loop.

I think they said it may turn 70 over the
weekend.

I don't know.

I heard different reports.

And yesterday was supposed to be a little
bit warm.

I don't know about you.

It was wet, cold, and clammy, and
freezing.

Wow.

Okay.

Bye, all.