Optimal Binary Search Trees Knuth

V

Varun

Guest
Varun Asks: Optimal Binary Search Trees Knuth
Knuth, Donald E. (1971), "Optimum binary search trees", Acta Informatica 1 (1): 14–25,doi:10.1007/BF00264289

Please have a look at this paper, specifically page 18 in which he tries to prove his lemma that $R_{0,n-1} \leq R_{0,n} $ here $R$ refers to the minimal optimal node which will be the root of the binary tree containing elements $a_{0} ... a_{n} $ .

I understood the idea of the proof using induction that for some $k \, j_{k}=i_{k} $ . Now the next part of the proof is cutting and replacing,I have understood perfectly till there. What i don't understand is how $F''$ weighted path length is equal to weighted path length of $F'$ for all $a_{n}$. Can anyone please give me a hint or a solution to that.

SolveForum.com may not be responsible for the answers or solutions given to any question asked by the users. All Answers or responses are user generated answers and we do not have proof of its validity or correctness. Please vote for the answer that helped you in order to help others find out which is the most helpful answer. Questions labeled as solved may be solved or may not be solved depending on the type of question and the date posted for some posts may be scheduled to be deleted periodically. Do not hesitate to share your thoughts here to help others.
 

Unreplied Threads

How to combine nlp and numeric data for a linear regression problem

davidm Asks: How to combine nlp and numeric data for a linear regression problem
I'm very new to data science (this is my hello world project), and I have a data set made up of a combination of review text and numerical data such as number of tables. There is also a column for reviews which is a float (avg of all user reviews for that restaurant). So a row of data could be like:

Code:
{ 
    rating: 3.765, 
    review: `Food was great, staff was friendly`, 
    tables: 30, 
    staff: 15, 
    parking: 20
    ... 
}

So following tutorials, I have been able to do the following:

  1. Created a linear regression model to predict rating with the inputs being all the numerical data columns.
  2. Created a regression model to predict rating based on review text using sklearn.TfidfVectorizer.

But now I'd like to combine models or combine the data from both into one to create a linear regression model. So how can I utilize the vectorized text data in my linear regression model?

SolveForum.com may not be responsible for the answers or solutions given to any question asked by the users. All Answers or responses are user generated answers and we do not have proof of its validity or correctness. Please vote for the answer that helped you in order to help others find out which is the most helpful answer. Questions labeled as solved may be solved or may not be solved depending on the type of question and the date posted for some posts may be scheduled to be deleted periodically. Do not hesitate to share your thoughts here to help others.

[Solved] Trimble Data Transfer won't convert files

  • Tiago Cavalcante
  • Geography
  • Replies: 0
Tiago Cavalcante Asks: Trimble Data Transfer won't convert files
I was importing files from Trimble Recon for over 3 years and this never happened with me.

When I conect my controller and select the file to import, the file load 100% and when start to convert appear this error. I tried in 5 computers and 4 controllers recon too.

Asked to local support but they can't find the solution.

enter image description here

SolveForum.com may not be responsible for the answers or solutions given to any question asked by the users. All Answers or responses are user generated answers and we do not have proof of its validity or correctness. Please vote for the answer that helped you in order to help others find out which is the most helpful answer. Questions labeled as solved may be solved or may not be solved depending on the type of question and the date posted for some posts may be scheduled to be deleted periodically. Do not hesitate to share your response here to help other visitors like you. Thank you, solveforum.

Is there an equation depicting a compressible fluid flowing into a cone, increasing in pressure and velocity as the cone narrows?

  • Aneikei
  • Physics
  • Replies: 0
Aneikei Asks: Is there an equation depicting a compressible fluid flowing into a cone, increasing in pressure and velocity as the cone narrows?
I'm trying to write an equation which shows a compressible fluid entering a cone with radius R and length L, where the pressure (density) and velocity of the compressible fluid increases as the exit radius R' narrows, a huge bonus would be given the mass of the fluid to also be able to calculate the overall mass of the fluid based on the volume of the cone.

Thank you so much in advance. Also, this is not for homework. It's for a pet project I'm working on.

SolveForum.com may not be responsible for the answers or solutions given to any question asked by the users. All Answers or responses are user generated answers and we do not have proof of its validity or correctness. Please vote for the answer that helped you in order to help others find out which is the most helpful answer. Questions labeled as solved may be solved or may not be solved depending on the type of question and the date posted for some posts may be scheduled to be deleted periodically. Do not hesitate to share your thoughts here to help others.

Multiplicity of a holomorphic map at every point is one

Spectrum Asks: Multiplicity of a holomorphic map at every point is one
Let $F$ be a holomorphic map between two compact Riemann surface $X,Y$. Assume for each point $p\in X , mult_p(F)=1$. Then ,what can we say about the degree of that map (deg(F))?

Locally $F$ looks like a coordinate chart function. Can we say $F$ is an isomorphism? I am reading "Riemann Hurwitz formula " this question came in my thought but unable to get answer.

SolveForum.com may not be responsible for the answers or solutions given to any question asked by the users. All Answers or responses are user generated answers and we do not have proof of its validity or correctness. Please vote for the answer that helped you in order to help others find out which is the most helpful answer. Questions labeled as solved may be solved or may not be solved depending on the type of question and the date posted for some posts may be scheduled to be deleted periodically. Do not hesitate to share your thoughts here to help others.

Prime Ideal Theorem implies Hahn Banach Theorem

mathlearner98 Asks: Prime Ideal Theorem implies Hahn Banach Theorem
I am reading Jech's Axiom of Choice, and there is this exercise: chapter 2 Problem 19:

Show that the Hahn-Banach Theorem follows from the Prime Ideal Theorem.

I came up with a (possibly wrong) proof, and my idea is essentially to mimic the proof of the implication "Prime Ideal Theorem $\implies$ Consistency Principle for Binary Mess" (the proof of this implication is in Jech's book chapter 2). Because I am a novice in this field, I really am not sure whether or not I am missing something, so I would really appreciate if you can point out if I am missing something.

Let $V$ be a real vector space and $X\subset V$ be a subspace. Let $p$ be a sublinear functional on $V$ and let $f$ be a linear functional on $X$ such that $f(x)\leq p(x)$ for all $x\in X$. Using Ultra Filter Theorem (which is equivalent to the Prime Ideal Theorem) we will show that there is a linear functional $F$ on $V$ such that $F(x)\leq p(x)$ for all $x\in V$ and $F\restriction_X=f$. We will use this lemma without proof (proof can be found at page 158 Folland):

Lemma A: For every $x\in V$, there is a linear functional $g$ on $X+\mathbb{R}x$ extending $f$ with $g(y)\leq p(y)$ for all $y\in X+\mathbb{R}x$.

Let $I$ be the set of all finite dimensional subspaces of $V$. Let $$M:=\{g:g\text{ is a linear functional on some }P\in I\text{ compatible with }f\text{ and }g(x)\leq p(x)\text{ for all }x\in P\}$$ From Lemma A, for each $P\in I$, there is some $g\in M$ with $\text{dom}(g)=P$. For each $P\in I$, let $M_P$ denote the set of all $g\in M$ such that $\text{dom}(g)=P$. We take $Z$ be the set of all functions $z$ such that:

a) $\text{dom}(z)\subset I$;

b) $z(P)\in M_P$ for each $P\in \text{dom}(z)$;

c) for any $P,Q\in \text{dom}(z)$, the functions $g_1=z(P)$ and $g_2=z(Q)$ are compatible.

Let $\mathbb{F}$ be the filter over $Z$ generated by the sets $$N_P=\{z\in Z:p\in \text{dom}(z)\}$$ $N_P$'s indeed do generate a filter over $Z$ because for $P_1,...,P_n\in I$, we know $N_{P_1}\cap \cdots\cap N_{P_n}$ is non-empty, as $P_1+\cdots+P_n$ is still a finite dimensional subspace of $V$, and hence there is some linear functional $g$ on $P_1+\cdots+P_n$ such that is compatible with $f$ and $g(x)\leq p(x)$ for all $x\in P_1+\cdots+P_n$. Then $z:=\{(P_i\to g\restriction_{P_i}):1\leq i\leq n\}$ is inside $N_{P_1}\cap\cdots\cap N_{P_n}$.

By the Ultra Filter Theorem, we may let $U$ be an ultra filter over $Z$ that extends $\mathbb{F}$. Now, fix $P\in I$. For each $g\in M_P$, denote $O_g:=\{z\in Z:z(P)=g\}$. Then note that $N_P=\bigcup_{g\in M_P}O_g$ and that $O_g$'s are pair-wise disjoint. Also, each $O_g$ is non-empty. So from the fact that $U$ is an ultra filter, there exists a unique $g\in M_P$ such that $O_g\in U$. Hence, for an arbitrary $P\in I$, we found a unique choice of a linear functional (which we denote by) $g_P$ defined on $P\subset V$.

We claim that $g_P$'s for $P\in I$ are pair-wise compatible. For $P,Q\in I$, we know $O_{g_P},O_{g_Q}\in U$. Hence, $O_{g_P}\cap O_{g_Q}\neq\emptyset$. This means $g_P$ and $g_Q$ are compatible. Now, if we take $F:=\bigcup_{P\in I}g_P$, then $F$ is the desired linear functional on $V$.

Thank you in advance for any help!

SolveForum.com may not be responsible for the answers or solutions given to any question asked by the users. All Answers or responses are user generated answers and we do not have proof of its validity or correctness. Please vote for the answer that helped you in order to help others find out which is the most helpful answer. Questions labeled as solved may be solved or may not be solved depending on the type of question and the date posted for some posts may be scheduled to be deleted periodically. Do not hesitate to share your thoughts here to help others.

Confusion Between Event Space and Probability

stats_noob Asks: Confusion Between Event Space and Probability
I am having difficulty understanding the difference between Event Space and Probability.

Initially, I had always thought the following. Consider rolling a 6-sided die once:

  • The Event Space : 1,2,3,4,5,6
  • The Probability : All Events have a Probability of 1/6

I thought everything made sense until I read the following passage:

" In frequentist theory probability of an event is relative frequencies of that event over a large number of repeated trials of the experiment in question. Therefore, the parameters of a distribution are fixed because they stay the same in all the repetitions of the experiment. In Bayesian theory, the probabilities are degrees of belief in that an event would occur for in a single trial of the experiment in question. The problem with frequentist definition of probability is that it cannot be used to define probabilities in many real world applications. As an example, try to define the probability that I am typing on an android smartphone. Frequentist would say that the probability is either 0 or 1 . While the Bayesian definition allows you to choose an appropriate number between 0 and 1."

The above passage claims that using the Frequentist definition of Probability, the probability of someone typing on an Android Smartphone is either 0 and 1 - whereas the Bayesian definition of Probability allows for the probability of someone typing on an Android Smartphone being between 0 and 1.

This is very confusing for me - in this question:

  • I would have initially believed that the "Event Space" is "either 0 or 1" whereas the Probability could be a number "between 0 and 1".
  • Furthermore, I am confused as to why the Frequentist definition forces you to believe that the probability is either 0 and 1, whereas the Bayesian definition allows you to believe that the probability is between 0 and 1.

To illustrate my logic - here is what is going on in my mind:

  • Suppose there are 1000 people in a room. We take a survey and find out that 543 people are using Android Smartphones and 457 people are using Apple Smartphones.
  • Now, we realize that there were actually 1001 people in this room and we had forgotten to survey one person. As an experiment, we would like to estimate the probability whether this person has an Android phone or an Apple phone. As a key and fundamental assumption, we assume that this new person is representative of the 1000 people we just surveyed.
  • A Frequentist would estimate that there is a 0.543 probability that this new person is using an Android Phone and could calculate a 95% Confidence Interval on 0.543. This Confidence Interval would tell the Frequentist that "if he could magically walk into 20 such similar rooms in different parallel universes and if he were to estimate the proportion of Android users - in 19 of these cases, the true proportion of Android users in each room would be contained in the corresponding 95% Confidence Intervals".
  • Regarding this new person that was not surveyed, the Frequentist could say that "if 100 new people were there, roughly 54 of them would be Android users - however, in the case of this single new person, this new person can either be an Android user or not: since 0.54 is technically closer to 1 compared to 0, I will guess that this new person is an Android user and I am 54% confident in my guess".
  • Now, suppose a Bayesian observes the same 543 people but is given some additional Prior information that "in larger populations similar to the people sitting in the room they are in, 71% people of such people are believed to be Android users". The Bayesian can incorporate this Prior information through the form of a Beta (alpha,beta) Probability Distribution and estimate the proportion of people to "truly" be Android users (e.g. based on his MAP calculations, he might get an estimate of 0.65). He can also use this information to estimate the probability that this new 1001th person is an Android user is actually 0.64.
  • However, this 1001th person is either an Android user not - the Bayesian can still believe that in 100 new people, 65 of them will be Android users, but he is still forced to make a choice whether this new person is an Android user or not. Since 0.65 is closer to 1 compared to 0, the Bayesian might also believe that this new person is Android user and might (falsely) feel more confident about his estimate.
  • The Bayesian can also create a 95% Credible Interval but it will have a slightly different interpretation - The Bayesian can believe that there is a 0.95 probability that the true proportion of Android users in a similar population is contained within the 95% Credible Interval that he calculated. However, the Bayesian has no means of walking into parallel universes and repeating this experiment many times.

After this lengthy (and likely incorrect) summarization of my understanding - I reached the following conclusions:


  • In this Android Phone problem, the Event Space is either "1 or 0" (yes or no), but the Probability of these events is between "1 or 0" - regardless of the Frequentist or the Bayesian Interpretation of probability.


  • Assuming I am correct (which I am not) - how is the Bayesian definition of Probability any more flexible and versatile compared to the Frequentist definition of Probability?

Thanks!

Notes:


SolveForum.com may not be responsible for the answers or solutions given to any question asked by the users. All Answers or responses are user generated answers and we do not have proof of its validity or correctness. Please vote for the answer that helped you in order to help others find out which is the most helpful answer. Questions labeled as solved may be solved or may not be solved depending on the type of question and the date posted for some posts may be scheduled to be deleted periodically. Do not hesitate to share your thoughts here to help others.

The points of inflection are of order $1$ or $3$

  • Frederick Manfred
  • Mathematics
  • Replies: 0
Frederick Manfred Asks: The points of inflection are of order $1$ or $3$
I'm currently working on the book of Kirwan about "Complex algebraic curves" I don't understand this part of chapter 6.2:

enter image description here

I don't understand, why we can conclude that the point of inflection on $C_{\Lambda}$ are precisely the points of order $1$ or $3$. I guess, that order $3$ comes from the fact, that $p+p+p=0$ iff $p$ is an inflection point but what about order $1$? There we know nothing or do I oversee something?

SolveForum.com may not be responsible for the answers or solutions given to any question asked by the users. All Answers or responses are user generated answers and we do not have proof of its validity or correctness. Please vote for the answer that helped you in order to help others find out which is the most helpful answer. Questions labeled as solved may be solved or may not be solved depending on the type of question and the date posted for some posts may be scheduled to be deleted periodically. Do not hesitate to share your thoughts here to help others.
Top