f*********i
发帖数: 197 | 1 小弟在准备qualify考试，看到算法例卷上有三题，百思不得其解，希望高人能给一
点帮助。
1.You are given n items with weighs w[1..n] with w[1]
to group the items into m groups (1<=m<=n) non-empty and disjoint classes C1
,C2....Cm, and assign each item in Cj a weight-label Lj, 1<=j<=m, such that
EE(w[i]-Lj)^2 is minimun (汗，连加号打不出来，只好用E代替，1<=j<=m, w[i]
are the elements in each group j)
1)Give a pseudocode of an efficient algorithm to determine the Cj and the
label Lj, take w=[2,3,5,6,7,8,9,10], m=2 show L1,L2 a | K****n
发帖数: 5970 | 2 第二题不懂,先沿对角线走lg(n),确定半个横排半个竖排,再lg(n)不就好了?
第三个是非波那其再加个线性数组,所以还是exponential的?
want
C1
that
the
【在 f*********i 的大作中提到】
: 小弟在准备qualify考试，看到算法例卷上有三题，百思不得其解，希望高人能给一
: 点帮助。
: 1.You are given n items with weighs w[1..n] with w[1]: to group the items into m groups (1<=m<=n) non-empty and disjoint classes C1
: ,C2....Cm, and assign each item in Cj a weight-label Lj, 1<=j<=m, such that
: EE(w[i]-Lj)^2 is minimun (汗，连加号打不出来，只好用E代替，1<=j<=m, w[i]
: are the elements in each group j)
: 1)Give a pseudocode of an efficient algorithm to determine the Cj and the
: label Lj, take w=[2,3,5,6,7,8,9,10], m=2 show L1,L2 a
| K****n
发帖数: 5970 | 3 第一题,我感觉,简单一点儿用K-mean,复杂一点儿用mixture of gaussian
第二问还真是麻烦....
want
C1
that
the
【在 f*********i 的大作中提到】
: 小弟在准备qualify考试，看到算法例卷上有三题，百思不得其解，希望高人能给一
: 点帮助。
: 1.You are given n items with weighs w[1..n] with w[1]: to group the items into m groups (1<=m<=n) non-empty and disjoint classes C1
: ,C2....Cm, and assign each item in Cj a weight-label Lj, 1<=j<=m, such that
: EE(w[i]-Lj)^2 is minimun (汗，连加号打不出来，只好用E代替，1<=j<=m, w[i]
: are the elements in each group j)
: 1)Give a pseudocode of an efficient algorithm to determine the Cj and the
: label Lj, take w=[2,3,5,6,7,8,9,10], m=2 show L1,L2 a
| c*****t
发帖数: 1879 | 4 第二题就是从左下角开始从左往右从下往上走格子而已。
在 programming 版讨论过几次。。。
【在 K****n 的大作中提到】
: 第一题,我感觉,简单一点儿用K-mean,复杂一点儿用mixture of gaussian
: 第二问还真是麻烦....
:
: want
: C1
: that
: the
| K****n
发帖数: 5970 | 5 嗯,我抛个砖等待大牛们批判
【在 c*****t 的大作中提到】
: 第二题就是从左下角开始从左往右从下往上走格子而已。
: 在 programming 版讨论过几次。。。
| f*********i
发帖数: 197 | 6 第二题从左下到右上是只要logN,但是不一定能够找到X,在这次搜索以后，假设有A[i,j
]=i+1&&n>=j+1或者m
剩下的两个区域（左上和右下）还是要进行binary search，不止搜索两次，应该是搜
索多次啊
我去programming 版搜索看有没有相关的帖子 | l******e
发帖数: 470 | 7 1， dynamic programming.
k-means can't guarantee an optimal solution.
want
C1
that
the
【在 f*********i 的大作中提到】
: 第二题从左下到右上是只要logN,但是不一定能够找到X,在这次搜索以后，假设有A[i,j
: ]=i+1&&n>=j+1或者m: 剩下的两个区域（左上和右下）还是要进行binary search，不止搜索两次，应该是搜
: 索多次啊
: 我去programming 版搜索看有没有相关的帖子
| l******e
发帖数: 470 | 8 2, lower bound problem is always tricker..
we need adversary argument.
just consider this game, i play with adv.
in each round, i pick a element (i,j) from the matrix
then adv chooses to cover
either all elements (i',j') i'<=i and j'<=j
or all elements (i',j') i'>=i and j'>=j
How many step do i need to cover the whole n*n matrix.
this game is essentially equivalent to the problem, where I pick an element
and know which part of the matrix we don't need to consider any more.
To prove the game nee
【在 f*********i 的大作中提到】
: 第二题从左下到右上是只要logN,但是不一定能够找到X,在这次搜索以后，假设有A[i,j
: ]=i+1&&n>=j+1或者m: 剩下的两个区域（左上和右下）还是要进行binary search，不止搜索两次，应该是搜
: 索多次啊
: 我去programming 版搜索看有没有相关的帖子
| l******e
发帖数: 470 | 9 3, use generating functions to get the exact solution.
(the book <> has an excellent chapter on it)
or 2^n is a rough upper bound and fiboncci number (approxly 1.61^n) is a
lower bound
want
C1
that
the
【在 f*********i 的大作中提到】
: 第二题从左下到右上是只要logN,但是不一定能够找到X,在这次搜索以后，假设有A[i,j
: ]=i+1&&n>=j+1或者m: 剩下的两个区域（左上和右下）还是要进行binary search，不止搜索两次，应该是搜
: 索多次啊
: 我去programming 版搜索看有没有相关的帖子
| k******y
发帖数: 17 | 10 i am not quite sure about what you mean by ``bounding box''.
e.g. 3 \times 3 matrix
..*
...
*..
* represents an uncovered region
does the length of the smaller edge of the bounding box equal 3?
if i compare x with either one of them, the bounding box will become 1 \
times 1
my method is to consider the cells on the minor diagonal
if i compare x with a cell in the upper-left triangle,
adv answers x > that cell
if i compare x with a cell in the lower-right triangle,
adv answers x < that cell
if i
【在 l******e 的大作中提到】
: 2, lower bound problem is always tricker..
: we need adversary argument.
: just consider this game, i play with adv.
: in each round, i pick a element (i,j) from the matrix
: then adv chooses to cover
: either all elements (i',j') i'<=i and j'<=j
: or all elements (i',j') i'>=i and j'>=j
: How many step do i need to cover the whole n*n matrix.
: this game is essentially equivalent to the problem, where I pick an element
: and know which part of the matrix we don't need to consider any more.
| | | k******y
发帖数: 17 | 11 more details here
1. if there is only one class, prove that L = average of all items
recall some knowledge on quadratic functions
2. for any two classes, x1 < x2 < .. < x_n and y1 < y2 < .. < y_n
there exists an optimal solution in which
there is no k s.t. x1 < y_k < x_n or y1 < x_k < y_n
that means any two classes should be disjoint in some sense
the following lemma may help you to prove this:
if x1 + .. + x_{n - 1} < y2 + .. + y_n, then x_n cannot > y1
because otherw
【在 l******e 的大作中提到】
: 1， dynamic programming.
: k-means can't guarantee an optimal solution.
:
: want
: C1
: that
: the
| k******y
发帖数: 17 | 12 problem 3
\because T(n) = T(n - 1) + T(n - 2) + 1
\therefore T(n) + 1 = T(n - 1) + 1 + T(n - 2) + 1
Let S(n) = T(n) + 1
we have S(n) = S(n - 1) + S(n - 2), S(1) = S(2) = 2
so, S(n) = F(n - 1) and T(n) = S(n) - 1 = F(n - 1) - 1
want
C1
that
the
【在 f*********i 的大作中提到】
: 第二题从左下到右上是只要logN,但是不一定能够找到X,在这次搜索以后，假设有A[i,j
: ]=i+1&&n>=j+1或者m: 剩下的两个区域（左上和右下）还是要进行binary search，不止搜索两次，应该是搜
: 索多次啊
: 我去programming 版搜索看有没有相关的帖子
| c*****t
发帖数: 1879 | 13 You only proved your method is O (n), but you didn't prove the problem
lower bound solution is omega (n). It is a harder problem to prove.
【在 k******y 的大作中提到】
: i am not quite sure about what you mean by ``bounding box''.
: e.g. 3 \times 3 matrix
: ..*
: ...
: *..
: * represents an uncovered region
: does the length of the smaller edge of the bounding box equal 3?
: if i compare x with either one of them, the bounding box will become 1 \
: times 1
: my method is to consider the cells on the minor diagonal
| k******y
发帖数: 17 | 14 i did prove the lower bound of the problem by adversary method | l******e
发帖数: 470 | 15 i did say the sum of ...i have 2 bounding boxes
in your case, it is 2.
however, your argument is cleaner.
i am not quite sure about what you mean by ``bounding box''.
e.g. 3 \times 3 matrix
..*
...
*..
* represents an uncovered region
does the length of the smaller edge of the bounding box equal 3?
if i compare x with either one of them, the bounding box will become 1 \
times 1
my method is to consider the cells on the minor diagonal
if i compare x with a cell in the upper-left triangle,
adv an
【在 k******y 的大作中提到】
: i am not quite sure about what you mean by ``bounding box''.
: e.g. 3 \times 3 matrix
: ..*
: ...
: *..
: * represents an uncovered region
: does the length of the smaller edge of the bounding box equal 3?
: if i compare x with either one of them, the bounding box will become 1 \
: times 1
: my method is to consider the cells on the minor diagonal
| k******y
发帖数: 17 | 16 what is the meaning of a ``region'' in your proof?
a set of connected uncovered cells?
【在 l******e 的大作中提到】
: i did say the sum of ...i have 2 bounding boxes
: in your case, it is 2.
: however, your argument is cleaner.
:
: i am not quite sure about what you mean by ``bounding box''.
: e.g. 3 \times 3 matrix
: ..*
: ...
: *..
: * represents an uncovered region
| l******e
发帖数: 470 | 17 yes.
【在 k******y 的大作中提到】
: what is the meaning of a ``region'' in your proof?
: a set of connected uncovered cells?
| k******y
发帖数: 17 | 18 what about this one:
1234567
1**.....
2**.....
3.......
4...*...
5.......
6.....**
7.....**
i compare x with (4, 4)
the sum becomes 3 after the comparison
【在 l******e 的大作中提到】
: yes.
| l******e
发帖数: 470 | 19 . is uncovered region?
then L doesn't change...
【在 k******y 的大作中提到】
: what about this one:
: 1234567
: 1**.....
: 2**.....
: 3.......
: 4...*...
: 5.......
: 6.....**
: 7.....**
: i compare x with (4, 4)
| k******y
发帖数: 17 | 20 no * is uncovered region
【在 l******e 的大作中提到】
: . is uncovered region?
: then L doesn't change...
| | | l******e
发帖数: 470 | 21 how is that possible...
well, i didn't check my pf rigorously and it might be wrong, but i don't
have counterexample yet:)
【在 k******y 的大作中提到】
: no * is uncovered region
| k******y
发帖数: 17 | 22 ic, it seems impossible to generate such a strange unconvered region :)
anyway, bounding box is a creative way to think about questions like this
【在 l******e 的大作中提到】
: how is that possible...
: well, i didn't check my pf rigorously and it might be wrong, but i don't
: have counterexample yet:)
| f*********i
发帖数: 197 | 23 I still quite confused about the problem3,
for each search, koalawjy, you are using binary method, cost logN
however, after we find A[i,i]
with 2 covered and 2 uncover, then apply same method to these 2 uncovered
regions cause 4 smaller uncovered one, and so on.
the size of the regions becomes smaller and the number are bigger, how to
cope with it?
***************
if i compare x with a cell in the upper-left triangle,
adv answers x > that cell
if i comp | k******y
发帖数: 17 | 24 可能我沒有説明白
我並沒有提出我是要如何猜
而是在證明無論我如何猜，都至少需要n次
原因在於一次猜測至多只能排除掉副對角綫上的一個格子
如果我不能排除掉所有的格子，我的敵手(adv)就可以構造出一個讓我判斷失誤的情形
【在 f*********i 的大作中提到】
: I still quite confused about the problem3,
: for each search, koalawjy, you are using binary method, cost logN
: however, after we find A[i,i]: with 2 covered and 2 uncover, then apply same method to these 2 uncovered
: regions cause 4 smaller uncovered one, and so on.
: the size of the regions becomes smaller and the number are bigger, how to
: cope with it?
: ***************
: if i compare x with a cell in the upper-left triangle,
: adv answers x > that cell
| k*******g
发帖数: 3 | |
|
