2b simply say that if you have a graph G = (V,E), where V is a set of
vertices (V = {0,1,2,3,4,5}) and E is the set of edges ( E =
{(1,2),(3,4)}) where each edge has a weight - think of it as a length
between the vertices that this edge connects, if it's easier. So show this
graph - make 6 points, name them 0 through 5 and connect 1-2 and 3-4.
That's it... That's all you need about definition of Graph. Now try to
come up with situations where your input size would be n+m and n+m+(other
stuff)... It's not hard...

Vitaly...

In article ,
Lyle Waldman wrote:

This course will assume you know a bit of graph theory.
MATH 239 is a prerequisite. If you lack the prerequisite, please
catch up on your own -- read ahead in your 239 notes, try a Graph Theory text,
look in your Algorithms text, try wikipedia, etc. You need very
little for 2B -- just the definition of a graph.

The question 6 said "matrix Mi has ki rows and ki+1 columns. I'm quite
confused about this. is ki+1: k(i+1) or (ki) + 1? What is k? Thanks.

HI all,

By looking at the notes taken from class, it is not obvious to see the
pattern of the proof easily.
It would be great if anyone or TA could provide a summary of the
procedures to prove the correctness of the Greedy Algorithm in
general. THanks.

Would anyone be able to lend / scan me a copy of the lecture notes from
Sept 16? Please and thank you.

Could anyone borrow me the notes from the first lecture so that I
could make photocopy of it? Greatly appreciate that!

1) I seem to remember from CS240 that there was a definition of Big-O
that used limits. I don't have my CS240 notes on me, and I forgot the
definition. I think it was something like f is O(g) if lim_n->inf(f/g)
<= 1, which I think makes intuitive sense. I'm not sure though. Does
anyone have these? They look to be really useful.

2) What is (log^2)n? I'm presuming it's (logn)^2.

3) Since I haven't touched Math138 for over a year (and barely touched
it even when I was taking it), I've completely forgotten my sequences
and series. Does anyone know the rule about the series n^k for k from 1
to inf? It was something like n < 0 -> series converges, but was there
any more to it?

Thanks. If I've said too much about any of the solutions, feel free to
moderate me, as I'm kinda getting back into the swing of newsgroups, and
never really used one for a non-programming course...

Lyle

Effective September 8, 2008, CS251 LEC 002 (11:30-12:50TTh) will be in MC1056
while CS341 LEC 001 (11:30-12:50TTh) will be in MC2038.

On one of the finals given, a question is:

True or False: The DP algorithm for coin changing runs in time
polynomial in the input size. Justify your answer.

From what I gather, a reasonable input size in this case would be
log(n), where n is the amount that we're trying to make change for.
The DP coin changing problem takes O(N*K), where N is the input value,
and K is the number of coins in the currency. However, this is not the
input size, so in fact would it not be O(k*2^n), and so the answer is
False (or am I completely missing something here)?

Was wondering if anyone else noticed this. I thought in class we
defined polynomial time reductions from decision problem to decision
problem. Clearly Q6 in both the sample exams, the questions asks for
a Turing polytime reduction from a non decision problem to a decision
problem - anyone know what they exactly mean here?

(From what I think they could mean, the Subset Sum to SSP should be
almost trivial and somehow would be worth 8 marks?)

Thanks