master的AD选择：EE@Yale or EE@CMU - 未名空间MITBBS历史存档

master的AD选择：EE@Yale or EE@CMU# EE - 电子工程

f*i2008-04-02 07:04

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

t*y2008-04-02 07:04

2 楼

这个公司如何？在vegas的那个，有前辈知道吗？多谢啦

y*72008-04-02 07:04

3 楼

耶鲁名气上大些，cmu的工科强些，怎么选择呢。。毕业后工作前景哪个更好些，请教~
~~

K*n2008-04-02 07:04

4 楼

第二题不懂,先沿对角线走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

t*o2008-04-02 07:04

5 楼

Sure, it is one of the top structural design firms in USA.

【在 t***y 的大作中提到】

: 这个公司如何？在vegas的那个，有前辈知道吗？多谢啦

y*72008-04-02 07:04

6 楼

哈，自己顶下~
其实EE名校出来工作是都不成问题的，只是想既然都要自费读硕士了，哪个的投资会有
更高的回报率呢~~
谢谢大家的意见呀！

K*n2008-04-02 07:04

7 楼

第一题,我感觉,简单一点儿用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

r*e2008-04-02 07:04

8 楼

cmu不清楚，yale的EE就是上8门课拿学位，而且也没啥好课...

教~

【在 y***7 的大作中提到】

: 耶鲁名气上大些，cmu的工科强些，怎么选择呢。。毕业后工作前景哪个更好些，请教~
: ~~

c*t2008-04-02 07:04

9 楼

第二题就是从左下角开始从左往右从下往上走格子而已。
在 programming 版讨论过几次。。。

【在 K****n 的大作中提到】

: 第一题,我感觉,简单一点儿用K-mean,复杂一点儿用mixture of gaussian
: 第二问还真是麻烦....
:
: want
: C1
: that
: the

l*e2008-04-02 07:04

10 楼

我选CMU：工科强大，选课方便，课程质量高（我推测的）。
如果是个女生，想混个工科学位，将来转市场或其他什么行当，去耶鲁吧。（即使是商科，CMU 也不比耶鲁弱很多，都是top 20.）

K*n2008-04-02 07:04

11 楼

嗯,我抛个砖等待大牛们批判

【在 c*****t 的大作中提到】

: 第二题就是从左下角开始从左往右从下往上走格子而已。
: 在 programming 版讨论过几次。。。

c*l2008-04-02 07:04

12 楼

去yale,其他机会多

【在 y***7 的大作中提到】

: 哈，自己顶下~
: 其实EE名校出来工作是都不成问题的，只是想既然都要自费读硕士了，哪个的投资会有
: 更高的回报率呢~~
: 谢谢大家的意见呀！

f*i2008-04-02 07:04

13 楼

第二题从左下到右上是只要logN,但是不一定能够找到X,在这次搜索以后，假设有A[i,j
]=i+1&&n>=j+1或者m剩下的两个区域（左上和右下）还是要进行binary search，不止搜索两次，应该是搜
索多次啊
我去programming 版搜索看有没有相关的帖子

y*72008-04-02 07:04

14 楼

背景是一女生，但是没有想好毕业后要转别的，因为不知道自己适不适合，目前基本打
算是毕业后找个专业相关点方向先工作再说吧。。。
怎么说Yale机会多呢，就工科而言CMU在工业界的口碑应该很好很好的吧，所以CMU机会
也应该很多呀

l*e2008-04-02 07:04

15 楼

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*e2008-04-02 07:04

16 楼

小水葱的说的“机会”意思是转金融、法律什么的，也就是我前面说的转别的行当，毕
竟耶鲁人文方面的校友多、口碑好。那也是个选择。
如果想做本行，毫无疑问选CMU，比yale高出一个档次。
这个概念有点像清华和北大的电子相比较。或者北邮跟南大相类比。
耶鲁电子课程选择面很窄，如果你想学真东西，会感觉不够爽。

l*e2008-04-02 07:04

17 楼

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 版搜索看有没有相关的帖子

c*l2008-04-02 07:04

18 楼

现实点说吧，没准你去yale嫁一牛人，连奋斗都不用了

【在 y***7 的大作中提到】

: 背景是一女生，但是没有想好毕业后要转别的，因为不知道自己适不适合，目前基本打
: 算是毕业后找个专业相关点方向先工作再说吧。。。
: 怎么说Yale机会多呢，就工科而言CMU在工业界的口碑应该很好很好的吧，所以CMU机会
: 也应该很多呀

l*e2008-04-02 07:04

19 楼

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 版搜索看有没有相关的帖子

L*e2008-04-02 07:04

20 楼

Yale is a big name, think about it, 6 presdients are your alumni.
What a great thing.
Industry doesn't care school that much, you have to show your
real skills, otherwise, CMU still doesn't mean anything.
To me, CMU is worse than stanford and mit,hehe.

【在 y***7 的大作中提到】

: 背景是一女生，但是没有想好毕业后要转别的，因为不知道自己适不适合，目前基本打
: 算是毕业后找个专业相关点方向先工作再说吧。。。
: 怎么说Yale机会多呢，就工科而言CMU在工业界的口碑应该很好很好的吧，所以CMU机会
: 也应该很多呀

k*y2008-04-02 07:04

21 楼

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.

l*e2008-04-02 07:04

22 楼

我觉得，将来真正能起作用，是行业内的校友，其他专业的校友对自己来说都是虚名而
已。
名校的重要性在于“业界”校友兼专业技能的培养。这就是为什么在通信行业，北邮学
生比北大电子系学生吃香的原因。

k*y2008-04-02 07:04

23 楼

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

c*l2008-04-02 07:04

24 楼

nod

【在 l*******e 的大作中提到】

: 我觉得，将来真正能起作用，是行业内的校友，其他专业的校友对自己来说都是虚名而
: 已。
: 名校的重要性在于“业界”校友兼专业技能的培养。这就是为什么在通信行业，北邮学
: 生比北大电子系学生吃香的原因。

k*y2008-04-02 07:04

25 楼

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 版搜索看有没有相关的帖子

x*y2008-04-02 07:04

26 楼

agree on this. EE engineers really don't give a shit about how many
presidents come from your school. They get the impression of a school
from co-workers,
publications, conferences, etc.

【在 l*******e 的大作中提到】

: 我觉得，将来真正能起作用，是行业内的校友，其他专业的校友对自己来说都是虚名而
: 已。
: 名校的重要性在于“业界”校友兼专业技能的培养。这就是为什么在通信行业，北邮学
: 生比北大电子系学生吃香的原因。

c*t2008-04-02 07:04

27 楼

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

L*e2008-04-02 07:04

28 楼

the problem with pku ee is they are too theoretical and not engineering
enough.
pku is not comparable to yale, either.
pku alumni is a very loose group that you can't count on.
I believe yale is doing much better than them.

【在 l*******e 的大作中提到】

: 我觉得，将来真正能起作用，是行业内的校友，其他专业的校友对自己来说都是虚名而
: 已。
: 名校的重要性在于“业界”校友兼专业技能的培养。这就是为什么在通信行业，北邮学
: 生比北大电子系学生吃香的原因。

k*y2008-04-02 07:04

29 楼

i did prove the lower bound of the problem by adversary method

L*e2008-04-02 07:04

30 楼

compare bupt with pku is not fair.
bupt graduates maybe 200 students in telecomm.
while pku only produces 20 students go to work. others go abroad,
go to get a master, of which only maybe 10 every year go to telecomm.
Considering that bupt has more high level people in telecomm and
get promoted faster than pku ee, no wonder pku ee get very low
voice for themselves. pku also has a big enemy thu, so that it's very hard
for them to survive in the conflicts.
Actually maybe half of pku ee guys go to

【在 l*******e 的大作中提到】

: 我觉得，将来真正能起作用，是行业内的校友，其他专业的校友对自己来说都是虚名而
: 已。
: 名校的重要性在于“业界”校友兼专业技能的培养。这就是为什么在通信行业，北邮学
: 生比北大电子系学生吃香的原因。

l*e2008-04-02 07:04

31 楼

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

r*s2008-04-02 07:04

32 楼

八门课就拿学位了？2学期就万事了？多少钱一门课？

【在 r*****e 的大作中提到】

: cmu不清楚，yale的EE就是上8门课拿学位，而且也没啥好课...
:
: 教~

k*y2008-04-02 07:04

33 楼

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*e2008-04-02 07:04

34 楼

yes.

【在 k******y 的大作中提到】

: what is the meaning of a ``region'' in your proof?
: a set of connected uncovered cells?

k*y2008-04-02 07:04

35 楼

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*e2008-04-02 07:04

36 楼

. 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*y2008-04-02 07:04

37 楼

no * is uncovered region

【在 l******e 的大作中提到】

: . is uncovered region?
: then L doesn't change...

l*e2008-04-02 07:04

38 楼

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*y2008-04-02 07:04

39 楼

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*i2008-04-02 07:04

40 楼

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*y2008-04-02 07:04

41 楼

可能我沒有説明白
我並沒有提出我是要如何猜
而是在證明無論我如何猜，都至少需要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*g2008-04-02 07:04

42 楼