eho0n3

But then the event "executing another U" has different probabilities. Shouldn't it have the same probability every time? Maybe the problem is my notion of "expected value". I've never encoutered a problem where the random variable is constant. Can you provide another example where the random variable is constant?

You didn't calculate a weighted average. If you did calculate an expected value, shouldn't it look like (1)1 + (1/2)2 + (1/4)3 + (1/8)4 + ...

Interesting, but why do you add the probabilities? You are basically saying that the probability of U exectuing once, or twice, or thrice, etc. is 2 (which doesn't even make sense).

I am not understanding question 34 on the GRE CS Practice Test Form GR0329. The question asks "What is the expected number of times that U executes?" where U is the entry node in the CFG in the question. The options are (A) 0.5, (B) 1, © 1.5, (D) 2, and (E) More than 10. I remember covering CFGs when learning about cyclomatic complexity but I don't remember studying about CFGs having edges with execution-probabilities. Options (A) and © don't make any sense so I can ignore those. Since U is the first statement at the beginning of a "do...while" loop, it executes at least once. However, I don't know how to use the probabilities given to find the number of times U executes. How can I know the number times U executes without knowing the number of times the "do...while" loop executes?

May I ask why you are taking the TOEFL and the TSE? Apart from that, your profile looks great. You say your GRE score for the subject test will reach the grad. dept. after the deadlines, but what is the deadline? (If the deadlines are between Dec. and Jan., I don't see the problem.)

The point I was trying to make is that people are raising what a "decent GRE score" is. On another topic, I was told yesterday by a taiwanese acquaintance that he took the GRE test to enter grad. school long ago and got a score of 2100/2400 which is equivalent to a 1400 nowadays. Because of his score, they decided to give him a teaching assistantship, but after a couple of classes as a TA he lost his TA position because nobody could understand what he was saying (because his english was horrible) so they gave him another job. He laughed as he told me this. I found the situation rather comical as well.

Congratulations on your score. Unfortunately it is people like you that keep raising the bar on these tests and now I have to study harder to match if not surpass your score (please don't take this personally). It makes me wonder what would happen if the average score dropped considerably. Would institutions lower their requirements? Would ETS change the test? What would happen?

I'm not sure but I think you will have to retake it. I'm in a similar predicament (took the TOEFL back in 1999), but I don't think I need it anymore since I am a U.S. university graduate (which means I speak fairly good english).

No. No.

I suggest you retake it. You want to get at least a 1400 on the GRE. I know since I'm also retaking it because of my "bad" score. You need to improve your verbal score big time.

I'm not saying the 7th largest element is the root of the tree or located in the right subtree in your example. I'm saying that the 7th largest element will be on this tree (because the rightmost subtree at height h - 3 starts at the root, so the whole of the tree is the rightmost subtree). Maybe I'm not communicating properly here. I'm not sure how I can further clarify myself.

Backtracking seems exceedingly complex. I prefer my simpler method. There are balanced binary trees and complete balanced binary trees. Every node in a complete balanced binary tree has two children, except for the leaves. A balanced binary tree (more specifically a height balanced binary tree) is such that the difference in height of a node's left and right subtree is at most 1.

Has anybody ever taken the GRE for the first time with little to no preperation and managed to score over 1400? I took it last year and obtained Verbal: 460 Quantitative: 750 AWA: 4.5 I downloaded POWERPREF about a month before the exam and did every practice section/test just to get a feel for the exam. As you can see though, my scores suck. I'm thinking about taking it again this year so I can increase my verbal score, but the only way this seems possible is if I become a walking english dictionary. Why does ETS do this?

Try to get in as much discrete maths., comp. arch., and data structures/algorithms under your belt. Next I recommend studying some software eng. and networking. Know enough of these subjects and you should do very well on the test.

Try to be as overprepared as possible. Don't leave anything to chance.

I disagree completely. About half of the elements in the tree larger than the root will be on root's right subtree (by definition) and the other half (which is smaller than the root) will be in the root's left subtree. If the root's right subtree has more than six elements, the 7th largest element is guaranteed to be in the root's right subtree. You don't need to search for the largest element in a binary search tree. The largest element will always be the rightmost node in the tree. Also, you can't backtrack to find the other larger elements. For example, the 3rd largest element may be the 1st largest element's parent's left child (i.e. the largest element's sibling). How can you back track to this node?

Could someone explain how to find the 7th largest element using data structure iii (I'm assuming the tree is not completely balanced)? If h is the height of the tree, then I know the 7th largest element will be in the rightmost sub-tree at height h - 3. At this point, I would have to store the value of every node in this tree in an array (for example), and sort it (using mergesort so I'm guaranteed it will take time O(log n)) to find the 7th largest value. This is the only way I can think of.

I can send it to you if you want (via e-mail, irc, or whatever).

I think the usual data structures are the ones you learn in a course on data structures.

Silly me. You are right. Thanks.

Another aggrevating question: Consider the possible data structures for a set of n distinct integers. i. A min-heap ii. An array of length n sorted in increasing order iii. A balanced binary search tree For which of these data structures is the number of steps need to find and remove the 7th largest element O(log n) in the worst case? (A) i only (B) ii only © i and ii (D) i and iii (E) ii and iii I know i isn't an answer since the number of steps to find the 7th largest element is O(n log n) in the worst case. That leaves either (B) or (E). Now suppose A[0...n - 1] is representative of data structure ii. Because each A is distinct and A

Check out these link: http://www.brpreiss.com/books/opus4/html/page211.html, http://lcm.csa.iisc.ernet.in/dsa/node42.html, and http://lcm.csa.iisc.ernet.in/dsa/node43.html. These should resolve your hashing misunderstandings.

Nice one. Now I'm satisfied. Thanks.

No you don't need to search for it if you have the NODE (i.e. element) at your disposal (note emphasis on the word node). Now suppose each node stores an integer and you want to delete the node containing the integer k (i.e. the key k). In this situation, deletion will take time O(m/n). Can you now discriminate between the words element and key? I stand corrected. If k is a multiple of m, then h(k) = 0 as you mention. Now you have me confused. I'll have to look into this matter some more.

So your question basically boils down to: Why does deletion take O(1) time in a doubly-linked list? I suggest you look at the sequence of operations that implement the deletion procedure for a doubly-linked list in your book. I'm sure you will understand. Let me know if you need further clarification. Generally they are the same. The author is explaining that one need not search the hash table (using a key) to remove the element x. Because x is a node in some doubly-linked list in the hash table, one can do the deletion directly. Let me know if you need further clarification. The reason one chooses m as prime is to reduce clustering. Suppose m is a power of two and k > m. If k is a power of two then h(k) = 0, effectively creating a cluster at table location 0. If m were prime, the clustering at table location 0 is effectively reduced (for h(k) equals 0 only when k is a power of m and there are more k's in the latter situtation (when k and m are powers of two) than in the present one). If h generates values in the range 0 to m - 1 with equal probability, then h is effectively a perfect hash function. The division method for choosing h however is not known (at least to my knowlegde) to produce a perfect hash function. Hope that helps.