cjlax26

I attended a US school for my undergrad. By top 10, I meant a top 10 CS proram in the US.

Scores by phone are now available for the Nov. 8 test. I scored 720 / 48%... :( Should I even bother sending this score with my applications? I am applying for an MS to the following schools. Univ. of Texas Austin MIT Univ. of Cal Berkeley Univ of Cal SB Univ of Cal SD Univ. of Colorado Boulder The rest of my application should be fairly strong. I went to a top 10 school for undergrad and finished with a 3.75 overall gpa and a 3.9 CS gpa. My general GRE scores were 790 quantitative, 430 verbal (I know...) and 5.5 analytic writing. I have research experience at 2 top universities though no publications came out of either. I have pretty strong recommendations from 2 of my undergrad professors and 1 from a summer research program mentor. I also have 2 years industry experience if this matters. Any suggestions on whether to send in my AGRE scores to any of these universities? Will my score hurt my application? Will my application be strong enough for any of these schools? Thanks in advance!

The answer would only be A if you had an algorithm to convert ANY nfa to a dfa using the same number of states (or less) in the nfa. This is not possible... The question did not ask, "is it possible to convert an nfa to a dfa in N states". This is clearly possible, just consider an nfa with a single state for example. The question instead asks, "what is the minimum number of states to convert ANY nfa with n states to a dfa". I read this as "Given ANY nfa, what is the minimum number of states required." Meaning you don't know what nfa you will be given, could be ANY nfa. We could just be arguing semantics here though. Update: Also, just to reiterate, if the question had in fact meant "What is the minimum number of states needed to convert some nfa with N steps to a dfa" then the answer would be "1" and not "n" since we could certainly consider an nfa with n states that doesn not accept any strings (no accepting state). This nfa could be converted to a dfa with 1 state that just loops to itself (non accepting).

Answer should be C. Question states the min. number of states for ANY NFA to DFA (ANY in big letters).

Here is an easy way of looking at this problem: I. The set of all functions mapping N to {0,1} are all of the different functions that you can imagine for mapping the Naturals to a set of 2 elements. Consider a function from N to {0,1} to be a subset of N (lets just say a subset of elements of N that map to 0). Imagining all of these subsets equates to the Power set of N which has cardinality equal to the Reals which is uncountable. II. Here, we are dealing with functions that map {0,1} to N. This would be all of the subsets of N that have 2 elements. This in turn can be thought of as the set of all rational numbers (1/2, 1/3, 4/16, ...., etc.) The set of rational numbers is countable (there's a cool proof of this in Sipser) therefore this set is countable. III. The largest subset of N is N itself so this is kind of trivial as it is, but any subset of a countable set is also countable. A subset is always less than or equal in size.