Posted by: atri | October 4, 2010

HW 4 and a new category

There is a correction in HW 4: in Q 2, for the function $f(d)$, you should assume that $d\ge 2$. The online version of HW 4 has been updated to reflect this.

I have also added a new category: not student post. If you click on this category on the right frame (or on the link in the earlier sentence), then you’ll get a list of all posts that are not student posts. I have heard a few times that the student posts tend to overwhelm the other posts, so hopefully this’ll help. (This tag will go on for future posts so for the past one you might have to sift through other categories such as homework etc.)

Responses

1. There is a reference to (Note that this implies n = 2^d) in HWK #4 Question 2. Aside from a vertex count, what is the relevance of N?

• Hi Kris,

Not much really. Just wanted to make sure that you all understood that there are $2^d$ vertices in a $d$-dimensional hypercube.

2. Thanks,

Is the function the Question #2 mentions a function that Constructs a d-dimensional hypercube or is the function mentioned a function that takes as it’s it input a d – dimensional hypercube? Or something else?

• Hi Kris,

$f(d)$ does NOT construct a $d$-dimensional hypercube. It is just a function whose input is $d$, i.e. $f$ is a function from positive integers to positive integers. The problem asks your function $f(d)$ to have the following property: for every $d\ge 2$, the $d$-dimensional hypercube has a cycle of length at least $f(d)$.

3. Thanks!

Is a cycle defined after the 2nd reference to an originating node or can a cycle contain an arbitrary number of iterations around similar or distinct paths originating and terminating at a given vertex?

• Kris,

As we defined in class, all vertices in a cycle are unique except the last one, which is the same as the first one. So the length of a cycle is the number of edges encountered when making “one round” of the cycle.