text:
# Low Dimensional Topology

## October 13, 2013

### A noteworthy knot simplification algorithm

Filed under: Computation and experiment,Knot theory — dmoskovich @ 8:26 am

This post concerns an intriguing undergraduate research project in computer engineering:

Lewin, D., Gan O., Bruckstein A.M.,
TRIVIAL OR KNOT: A SOFTWARE TOOL AND ALGORITHMS FOR KNOT SIMPLIFICATION,
CIS Report No 9605, Technion, IIT, Haifa, 1996.

A curious aspect of the history of low dimensional topology are that it involves several people who started their mathematical life solving problems relating to knots and links, and then went on to become famous for something entirely different. The 2005 Nobel Prize winner in Economics, Robert Aumann, whose game theory course I had the honour to attend as an undergrad, might be the most famous example. In his 1956 PhD thesis, he proved asphericity of alternating knots, and that the Seifert surface is an essential surface which separates alternating knot complements into two components the closures of both of which are handlebodies.

Daniel Lewin is another remarkable individual who started out in knot theory. His topological work is less famous than Aumann’s, and he was murdered at the age of 31 which gives his various achievements less time to have been celebrated; but he was a remarkable individual, and his low dimensional topology work deserves to be much better known.

Before discussing his low dimensional topology, let me tell you a little bit about Daniel Lewin’s life, which you can read more about in this book. Daniel came from Colorado to Israel, where he joined the army and became a captain in Sayeret Matkal, which is Israel’s most famous commando unit (“Who dares wins!”). He then married and entered university to study computer engineering. As an undergrad at the Technion, he and his wife were dirt poor, and he had to work part-time at IBM to make ends meet. While supporting a family, working, and studying (incredible!), he wrote an undergraduate research project together with Orly Gan, under the tutelage of Alfred Bruckstein, on knot theory. Alfred “Freddy” Bruckstein is currenlty at NTU where I am, and it was from him that I learnt of this remarkable project. With it, Daniel Lewin won the Outstanding Student in Computer Engineering in 1995 (remember, in poverty, while supporting a family and working part-time!), and was able to get into MIT.

At MIT, Daniel Lewin and his advisor F. Thomson Leighton solved a problem on how to direct traffic through an overloaded internet. Leaving academia behind (at least temporarily), they opened a company called Akamai and became billionaires. Daniel Lewin was on American Airlines Flight 11 when it was hijacked, and had his throat slit while attempting to stop the hikackers. As a captain in the Sayeret, he would have responded (“who dares wins”, remember?)… and had he succeeded, which I think certainly might have been, then the plane would never have crashed into the North Tower of the World Trade Center, and perhaps 9-11 and all that came after it might never have happened the way that it did.

So what did Danny Lewin do? The main problem in knot theory is knot classification, whose core is knot recognition. Given two hopelessly complicated tangled pieces of rope with their ends fused together, do they or do they not represent the same topological knot? One way to answer this question would be to find an efficient algorithm to simplify both knots as much as possible, until they both end up in some minimum energy state and look the same’. This is something that knot theorists care very much about, and there are a number of approaches available:

1. Moebius energy is an knot energy (a functional on the space of knots in 3-space) which is particularly well-behaved. One may model the knot by a ball-and-stick model in 3-space, place simulated electric charges’ on the balls, and allow the configuration to find its minimal energy state. This leads to pretty and symmetrical knot embeddings. John Sullivan made a very nice computer algorithm along these lines, exhibited in this video. Thanks to Ian Agol for hosting it and for mp4 conversion!
2. Approaches using Pachner moves on triangulations. Pachner moves are combinatorial moves between triangulations, in this case of knot complements. Experimentally, these techniques can be highly effective, as exhibited in this paper by Ben Burton.
3. Dynnikov’s algorithm, which involves presenting the knot as a diagram on a 3-page book’, i.e. as a diagram on a collection of 3 half-planes meeting along a line. The knot diagram is then simplified using combinatorial moves. Book Knot Simplifier is a software package by Maria Andreeva, Ivan Dynnikov, Sergey Koval, Konrad Polthier, and Iskander Taimanov which uses this approach. At the moment, as far as I can see, this seems to be the state of the art.
4. The approach that Lewin, Gan, and Bruckstein take, based on the Dowker notation.

Lewin, Gan, and Bruckstein, being computer engineers and therefore unfettered by topological preconceptions, take a very interesting approach to the problem which from their perspective is very natural, and is quite direct. First, they present the knot using a modified Dowker notation, which is compact and easy to work with. Then, they simplify the modified Dowker notation using Reidemeister moves. How exactly do they do this? Why don’t they hit global minima? Here is where the skills of an engineer come into their own. The solution chosen by Lewin, Gan, and Bruckstein is to apply a simulated annealing algorithm.

Note that this is not the first time simulated annealing was used to simplify knots- there is a knot energy approach using simulated annealing due to Ligocki and Sethian. That approach suffers from some convergence issues because the knot is 3-dimensional and there are too many variables. A modification of this technique by Ladd and Kavlaki (robotics people!) using a stick presentation of knots in 3-space instead, and seems to give very nice results.

Simulated annealing is a probabilistic technique to find a global optimum for a function. Wikipedia says:

The name and inspiration come from annealing in metallurgy, a technique involving heating and controlled cooling of a material to increase the size of its crystals and reduce their defects, both are attributes of the material that depend on its thermodynamic free energy. Heating and cooling the material affects both the temperature and the thermodynamic free energy. While the same amount of cooling brings the same amount of decrease in temperature it will bring a bigger or smaller decrease in the thermodynamic free energy depending on the rate that it occurs, with a slower rate producing a bigger decrease.

In our case, the goal is to find the modified Dowker presentation with the fewest crossing, and the one that is most alternating’ (by one of the Tait conjectures, which have been proven, an alternating knot diagram is minimal, and so finding one solves the recognition problem). The type of simulated annealing that they use is called Bolzmann annealing. The knot is `cooled’, performing Reidemeister moves at random locations. If we get a lower energy diagram, go to that. Otherwise, accept it with a probability of $\left(1+e^{\frac{\Delta E}{kT}}\right)^{-1}$, or else stay put. So there are more jumps for higher temperatures, and the lower the temperature the energy the less probability there is of a jump. Lower the temperature, and repeat.

This is an undergraduate research project, and no theorems are proven. The algorithm, and even its application to knot theory, are not new. But using it on modified Dowker codes is certainly new. Experimentally, the algorithm appears to work extremely well. It’s extremely simple and robust, and entirely probabilistic, so it would work on huge knots as well as on small knots. Moreover, it’s massively flexible- it would work just as well for links, braids, tangles, virtual tangles, welded tangled objects, or just-about anything else. In particular, it works for tangle machines (while none of the other techniques do), which is why I’m particularly interested in it. I believe that it absolutely deserves to be much better known.

I wonder how close it is to being state-of-the-art even today- I asked a MathOverflow question about this, from which much of the information in this post is taken. As a random and irresponsible thought, wouldn’t it be interesting to have a software implementation challenge to see which algorithm could most rapidly simplify some arbitrary very complicated knot diagram with hundreds or even thousands of crossings? My money is on Lewin-Gan-Bruckstein.

1. A more classical 5th approach would be to start with the diagram, compute a presentation for the fundamental group of the complement, and try to simplify it to a presentation with no relators, using a variant of small cancellation theory. i.e. try to kill generators using relators, and shortening relators. If you get stuck, multiply relators together in various ways to try to find new useful relators. I suspect this can be very effective if implemented moderately intelligently.

Comment by Ryan Budney — October 13, 2013 @ 8:35 am

• This sounds like a very good idea! There would be a probabilistic approach, and a deterministic approach, here too.

Comment by dmoskovich — October 13, 2013 @ 8:48 am

2. Those of you interested in recognizing unknots, or the 3-sphere, or who are interested in simplifying general 3-manifold presentations might want to try a new version of Heegaard. (Eventually this may be posted on the website of Marc Culler and Nathan Dunfield.)

Heegaard accepts geometric presentations on up to 26 generators and 32 relators. So for knots, Wirtinger presentations, or geometric presentations obtained using over-crossing and under-crossing arcs will work provided the 26 generator restriction is satisfied.

In practice, Heegaard determines each of the following examples is unknotted in only a few seconds.

Thistlethwaite’s Unknot from Wikipedia, Culprit from Kaufmann-Lambropoulou, Fig5 from Kaufmann-Lambropoulou, H) from Henrich & Kauffman, J) from Henrich & Kauffman, G) Goeritz’s unknot, Ochiai’s unknot 1 from “Non-trivial projections of the trivial knot” URL http://hdl.handlenet/2433/99940, Ochiai’s unknot 2 from the same paper, and Freedman’s Twisted Unknot.

Those wishing to check such things for themselves can obtain a current copy of Heegaard from me by email request to jberge at charter ‘dot’ net.

Note Heegaard is a Unix executable, which runs under terminal on an apple macintosh. So you will probably need a mac.

Comment by John Berge — October 15, 2013 @ 4:37 am

3. Reblogged this on citedcorpse and commented:
This is a fascinating story, in any case.

Comment by citedcorpse — October 21, 2013 @ 2:19 pm

The Rubric Theme. Create a free website or blog at WordPress.com.


text:
Basic understanding of time

Recommended Posts

I disagree. I think it's getting too worked up about an analogy, and angry because someone is trying to understand a concept in a different way than you understand it. It's not meant to be taken literally. If someone is taking the analogy too far (e.g. thinking that time is made up of water molecules) then by all means take them to task for it, but the true test is whether you can do something correct with your understanding. So if "time flows" is useful for someone to understand something and they reliably come to the right conclusion when they apply it.

Share on other sites

Your challenge, I think, is to reconcile how time behaves objectively, as a physicist measures it and how you, as a psychologist, understand it relying more on human experiential and physiological data .

Well, yes, but don't misunderstand me - I'm not naively thinking that objective measures of time should map directly to subjective temporal perception. Even psychologists talk about "veridical" time as opposed to "subjective" time. I do think that we need to be aware that objective models of time arise from minds, and that our ideas about causality, for instance are rooted in the way we make sense of the world - in our intuitive models.

Share on other sites

I disagree. (And I am not alone, see below)

Fine, I didn't actually say I agreed or otherwise.

That quote was from the contibution to the book by one time particle physicist John Polkinghorne KBE, the quote started his analysis of the flow statement, in relation to the block universe (which I also linked to) which mirrors that here between Lizzie L and the hard physicists here.

Pretty well all aspects and all theories of the subject as discussed in this book by the range of experts indicated, including the originator of the light cone.

The other quote was from the objectives of the book.

It was all supplied in the spirit of adding informatuion for those who might wish to follow it up.

Share on other sites

Definitely a different beast. Which is why I've been arguing that we operationally define time, for scientific purposes, in terms of clocks. There doesn't seem to be a more fundamental definition than that.

Rather we quantify time based on oscillations because it is convenient. Another, perfectly valid oscillationless and far more fundamental definition of a unit of time is that of the planck time; the amount of time required for light to travel a planck length. We can use that as the unit length on a time ruler.

Share on other sites

Isn't the planck length defined in terms of the speed of light?

Share on other sites

Isn't the planck length defined in terms of the speed of light?

Yes it's $\sqrt{\frac{\hbar G}{c^3}}$

Share on other sites

In that case this definition:

Rather we quantify time based on oscillations because it is convenient. Another, perfectly valid oscillationless and far more fundamental definition of a unit of time is that of the planck time; the amount of time required for light to travel a planck length. We can use that as the unit length on a time ruler.

is circular.

Share on other sites

Isn't the planck length defined in terms of the speed of light?

I think all Planck units have c somewhere in the derivation. The most basic of the five equations with five universal constants is that

$l_P =ct_P$

In that case this definition:

is circular.

Yes - that's kind of the point. Everything both defines the other units and is in turn defined by them - they hang together as a self-referential, self-consistent, and self-contained set. That's why they are so neat.

Share on other sites

Yes - that's kind of the point. Everything both defines the other units and is in turn defined by them - they hang together as a self-referential, self-consistent, and self-contained set. That's why they are so neat.

It's also expected. It's why some units have to just be defined, rather than derived.

Share on other sites

It's also expected. It's why some units have to just be defined, rather than derived.

Is there anything you cannot get a planck unit of without further arbitrary definition (ie based on just h_bar, c, G, k_B, and 4.pi.epsilon_0). Luminoous Intensity ie like SI Candela?

Share on other sites

Is there anything you cannot get a planck unit of without further arbitrary definition (ie based on just h_bar, c, G, k_B, and 4.pi.epsilon_0). Luminoous Intensity ie like SI Candela?

Candela and mole, I think, are the SI base units not represented.

Share on other sites

It's also expected. It's why some units have to just be defined, rather than derived.

I don't have a problem with that.

Share on other sites

New here. Wow, 287 posts on this topic. Confession: I read the first 5 pages and the last page. I hope I do not repeat what others have posted.

I believe that what is usually called time is an artifact of memory. I think that saying this is not equal to saying that it is an illusion. Several posters connect time with change. Recognition of change requires memory, or another accepted record in place of one's own memory. I see the "passage of time" as recognition of change, but the "passage of time" is not the same as "time".

Einstein is quoted as saying that "time is what we see when we look at the face of a clock". I accept that he was correct. The face of a clock provides us with the state of an object (two objects if you prefer, the hands) relative to the state of another object, the face. What we see at any moment is just the face and the hands. In order to infer the passage of time, we must have some memory of what we saw at another moment. Additionally, we must have some confidence that we can tell which of the two observations was taken first. (Two photos of a clock showing different positions of the hands requires assumptions to infer any passage of time). Our experience tells us that the two observations cannot have been taken concurrently. (Two objects, the two sets of hands - one set in each photo - cannot have the same state).

So, what we see when we look at a clock is the state of the clock. Einstein said the state of the clock is time. Now, all objects have only one state, their current one. Objects do not have a past state or a future state. The current state of all objects is only "now", and thus time has only one state, the "now". I acept that we don't actually experience anything independent of the observed objects which we could call time. We only experience the objects. I conclude that time (not the passage of time) is the aggregate experience of a particular state, per Einstein: our experience of the face and the hands of the clock.

To be a bit more clear, I conclude that there is no phenomenon which we can call time. The term "time" is a shorthand way of describing our recognition of a particular state of existence.

Way too many words. Wrote this on-line. I hope it is not too disjointed.

Share on other sites

New here. Wow, 287 posts on this topic. Confession: I read the first 5 pages and the last page. I hope I do not repeat what others have posted.

I believe that what is usually called time is an artifact of memory. I think that saying this is not equal to saying that it is an illusion. Several posters connect time with change. Recognition of change requires memory, or another accepted record in place of one's own memory. I see the "passage of time" as recognition of change, but the "passage of time" is not the same as "time".

Einstein is quoted as saying that "time is what we see when we look at the face of a clock". I accept that he was correct. The face of a clock provides us with the state of an object (two objects if you prefer, the hands) relative to the state of another object, the face. What we see at any moment is just the face and the hands. In order to infer the passage of time, we must have some memory of what we saw at another moment. Additionally, we must have some confidence that we can tell which of the two observations was taken first. (Two photos of a clock showing different positions of the hands requires assumptions to infer any passage of time). Our experience tells us that the two observations cannot have been taken concurrently. (Two objects, the two sets of hands - one set in each photo - cannot have the same state).

So, what we see when we look at a clock is the state of the clock. Einstein said the state of the clock is time. Now, all objects have only one state, their current one. Objects do not have a past state or a future state. The current state of all objects is only "now", and thus time has only one state, the "now". I acept that we don't actually experience anything independent of the observed objects which we could call time. We only experience the objects. I conclude that time (not the passage of time) is the aggregate experience of a particular state, per Einstein: our experience of the face and the hands of the clock.

To be a bit more clear, I conclude that there is no phenomenon which we can call time. The term "time" is a shorthand way of describing our recognition of a particular state of existence.

Way too many words. Wrote this on-line. I hope it is not too disjointed.

I disagree.

Time is evrywhere in physics. Almost all equations include somewhere this little "t".

to me, time is a very real phenomenon. The problem is that we are embedded in time (and space), so we have to analyze from the inside, which is extremely difficult.

If you take a step back and think very deeply not about time anymore, but about space, you may find out that space is equally mysterious with time, although more easily 'touchable".

IMHO we (I mean the human beings) haven't grasp what it's all about, yet.

Share on other sites

One thing I know for sure is that you cannot think of time as of something that doesn't quantize, so there is some limit to the smallest amount of time we can have. if we have two runners one 1 m away from another, where the lagger runs twice as fast, we can make an argument that while the lagger gets to where the leader is, the leader will move a half meter, then by the same algorithm by 1/4 meter, etc. and according to such an argument the lagger will never catch the leader because he will always be (1/2)^n meters behind. we know what that series converges to, and we know that after the leader runs for approximately 1 m the lagger will catch up to him, but if time was indeed forever divisible it would never happen.

Share on other sites

One thing I know for sure is that you cannot think of time as of something that doesn't quantize, so there is some limit to the smallest amount of time we can have. if we have two runners one 1 m away from another, where the lagger runs twice as fast, we can make an argument that while the lagger gets to where the leader is, the leader will move a half meter, then by the same algorithm by 1/4 meter, etc. and according to such an argument the lagger will never catch the leader because he will always be (1/2)^n meters behind. we know what that series converges to, and we know that after the leader runs for approximately 1 m the lagger will catch up to him, but if time was indeed forever divisible it would never happen.

That does not follow from your explanation. There is no quantized unit or smallest length of time if you are solving this problem. You have a finite duration and an infinite number of intervals, which is inconsistent with a minimum length of time.

Share on other sites

That does not follow from your explanation. There is no quantized unit or smallest length of time if you are solving this problem. You have a finite duration and an infinite number of intervals, which is inconsistent with a minimum length of time.

Perhaps I did not make myself clear. Hmm. Ok. If you were able to divide time indefinitely you can look at the problem as an infinite sum of infinitely small quantities, that get smaller and smaller, and tend to 0. I think it is effectively a rhetoric of how you define limits, and you're right that in the case of such a series I suggested there is no ambiguity. Thank you for correcting me.

Share on other sites

I haven't read the whole thread, but it's fascinating to see people so fascinated by time. I give my opinion. Time is the various sequences of movement, is not a poetic dimension, but even Einstein I suppose was aware of this, even when he was talking about time or spacetime.

Share on other sites

I visualize time as a kind of virtual 4th dimension.

In Hinduism Shiva is said to have had a third eye that was endowed with extra-sensory perception.

Time exists as long as a "third-eye" is there to observe it.

Recall that there is no such thing as absolute time.

Time is observer dependent and without one, time ceases to exists (or could be visualized to be decoupled from space time) to leave space which is temporal and perceptible regardless of the observer.

I visualize time as "quantum time" !!!

Time is what the observer sees depending on what he wants to see, (frame of reference dependent).

Time both does and does not exist.

It exists when a observer conceptualizes it related to his frame of reference but in essence it actually does not exist !!!

Edited by petrushka.googol

Share on other sites

It is also very peculiar, that although according to Einstein's space time continuum and the whole concept of a four space, time behaves very different from position. You can always move an object to a negative direction in terms of position, but with time, although theoretically you can make calculations and predictions about what happened before right now, you can never go back to that particular moment.

Share on other sites

It is also very peculiar, that although according to Einstein's space time continuum and the whole concept of a four space, time behaves very different from position. You can always move an object to a negative direction in terms of position, but with time, although theoretically you can make calculations and predictions about what happened before right now, you can never go back to that particular moment.

I think it is a wrong interpretation. Negative direction is simply a rotation 180 degrees, it is not exactly a negative.

Truly negative space would be negative distance and we know that negative distance does not exist.

Share on other sites

It is also very peculiar, that although according to Einstein's space time continuum and the whole concept of a four space, time behaves very different from position. You can always move an object to a negative direction in terms of position, but with time, although theoretically you can make calculations and predictions about what happened before right now, you can never go back to that particular moment.

My thoughts on this :

As I have said before time is relative to the observer and our choice of reference axes are purely arbitrary. If we consider the direction of increasing entropy to be negative (correlated with state of greater disorder) then the big bang becomes our origin and we could assume that time actually is moving backwards with respect to it. (negative is correlated with increased magnitude of entropy). Hence we could assume that we are actually moving back in time. It is purely subjective. Back to the future anyone ?

Share on other sites

I think it is a wrong interpretation. Negative direction is simply a rotation 180 degrees, it is not exactly a negative.

Truly negative space would be negative distance and we know that negative distance does not exist.

Then what it means is you can't rotate 180º on the time axis.

Share on other sites

I think it is a wrong interpretation. Negative direction is simply a rotation 180 degrees, it is not exactly a negative.

Truly negative space would be negative distance and we know that negative distance does not exist.

I don't think that's a good way to look at it. We can always define an origin at some point in space, and in time. No matter where it is, we can always plot a position and time of a certain event that occured. Suppose that event occured right now. Any other event that we observe will be observed with a positive time separation from this current event. However in terms of space the location could vary in either positive or negative (or be the same) as the current event. Therefore it's not that you are defining negative distance, it is a negative position, which is compared to a certain origin which is completely possible, however it's not possible in terms of time. What petrushka.gogol said before makes sense, however us as living beings see, and consider direction of increasing entropy to be positive, and you can make an argument that it's the same as saying that for us time is always running in the positive direction. It would be really cool to do the whole back to the future thing though

Share on other sites

I don't think that's a good way to look at it. We can always define an origin at some point in space, and in time. No matter where it is, we can always plot a position and time of a certain event that occured. Suppose that event occured right now. Any other event that we observe will be observed with a positive time separation from this current event. However in terms of space the location could vary in either positive or negative (or be the same) as the current event. Therefore it's not that you are defining negative distance, it is a negative position, which is compared to a certain origin which is completely possible, however it's not possible in terms of time. What petrushka.gogol said before makes sense, however us as living beings see, and consider direction of increasing entropy to be positive, and you can make an argument that it's the same as saying that for us time is always running in the positive direction. It would be really cool to do the whole back to the future thing though

....

Edited by petrushka.googol

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

×
×
• Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.

format: plain


text:
# zbMATH — the first resource for mathematics

Martingale-based residuals for survival models. (English) Zbl 0692.62082
Summary: Graphical methods based on the analysis of residuals are considered for the setting of the highly-used D. R. Cox [J. R. Stat. Soc., Ser. B 34, 187-220 (1972; Zbl 0243.62041)] regression model and for the P. K. Andersen and R. D. Gill [Ann. Stat. 10, 1100-1120 (1982; Zbl 0526.62026)] generalization of that model. We start with a class of martingale-based residuals as proposed by W. E. Barlow and R. L. Prentice [Biometrika 75, 65-74 (1988; Zbl 0632.62102)]. These residuals and/or their transforms are useful for investigating the functional form of covariate, the proportional hazards assumption, the leverage of each subject upon the estimates of $$\beta$$, and the lack of model fit to a given subject.

##### MSC:
 62P10 Applications of statistics to biology and medical sciences; meta analysis 62M99 Inference from stochastic processes
Full Text:


text:
# How come we see a line when there isn't one in this picture?

I got this picture I generated myself and I don't understand how come we can see two diagonal lines when, I think, there is no actual lines.

Zooming in:

Center: Just another 2px wide square…

After thinking about it, I think it might come from the fact that, if you zoom really closely, it is only a succession of square, each time 2px smaller and of a different color.

Although there is no actual line directly built, we can see the corners of each square clearly and, together, our brain understand this as two diagonal lines. … I might just have answered my own question but I would appreciate your opinion/confirmation on this.

• That is so cool! I'm not sure what's going on any more... – anongoodnurse Jul 12 '15 at 3:07
• What is supposed to be in the center? Also what format are the pictures in and is there any compression? – StrongBad Jul 12 '15 at 15:09
• @StrongBad Added a picture of the center, just a 2px wide square. I generated it using PhotoImage in tkinter in Python, assigned each pixel one by one, creating the bigger square first then smaller and smaller (not very efficient, but pretty to watch it being built) then saved it as a png with PhotoImage.write, I don't know the compression or anything else, I left it by default. – JeromeJ Jul 12 '15 at 17:05
• My guess is it is a rendering artifact. The corner pixels have a different number of same color pixel neighbors from edge pixels, so they are in fact a different color when draw on the screen. – StrongBad Jul 12 '15 at 17:25
• @StrongBad I checked, it isn't. When I zoomed on the rendered picture (from a screenshot for instance) it looks exactly the same as when zoomed on the actual picture. Nice guess though, I didn't think about that. – JeromeJ Jul 13 '15 at 4:24

I can't zoom in on the picture, but what I see is bleeding from one color into the next along the diagonals (most evident in the green to blue and purple to red transitions). Are you saying that they are not there when you zoom in? I would think that because there is a gradient in the color transition, the gradient has to be emphasized in an angled meeting, more pronounced the sharper the angle (e.g.if it were a triangle, the angle would be 120° as opposed to 90°). It's not an optical illusion.

In short, you see two transecting lines on the diagonal because they are strongly suggested. The mind sees this accurately and reads the suggestion.

It is kind of like asking, why, in the following picture, do I read all the dotted lines as lines, where only two of them are actually solid lines?

Or, if you will, why do I see curves here?

Because the color differences in the offset squares are really there, suggesting a familiar curve, though in this question, it would be fair to ask Why do the curves appear smooth? In fact, the curves are not smooth.

If you do want to see interesting optical phenomenons,

• stare at the center of your image for 30 seconds, then scroll down to the blank area next to my diagrams. You will see squares of reciprocal colors not in your original (like a bright yellow.) Also interesting is that as the image fades, blinking will "refresh" it.

• after staring directly at the center for a minute or two, switch the focus very slightly to one side then back; you'll be pleasantly surprised by bursts of vibrant color parallel to each other each time you change.

Edited to add: This may be an optical illusion, but if it is, I'm unsure of what type it is. Looking at the zoomed image, clearly the impression is that there is some bleeding, but that's not the reality. Sorry I can't help more on this one. But it does get much more intriguing!

• Hi, thanks! I provided a zoom in in my question as suggested. – JeromeJ Jul 12 '15 at 2:59
• +1 for the answer. Please feel free to add some stuff from my chat if you think it fits your answer :) – AliceD Jul 12 '15 at 3:59
• @AliceD (Your chat? I know the reply wasn't directed to me but it left me curious!) – JeromeJ Jul 12 '15 at 6:27
• @JeromeJ - I was chatting with anongoodnurse about the bleeding of green in blue as well as the parallel lines within the colored bars. The parallel lines create a physical pattern and perpendicular edges in the corners. these two factor are enough to create an edge. It is not an illusion in my opinion. – AliceD Jul 13 '15 at 12:09


text:
7 views

If the transistors in the given figure have high values of $\beta$ and a $V_{B E}$ of $0.65$ volt, the current $I$, flowing through the $2$ kilo ohms resistance will be $\ldots .$


text:
# Find k pairs with smallest sums in Python

I'm trying to improve my Python, so I'm trying to do coding challenges and getting them reviewed. I would really appreciate if someone can point out how I can make my code cleaner/more pythonic. My min_heap with a 3-value tuple seems a bit messy, but I couldn't think of a better way to do it.

Problem:

https://leetcode.com/problems/find-k-pairs-with-smallest-sums/description/

You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k.

Define a pair (u,v) which consists of one element from the first array and one element from the second array.

Find the k pairs (u1,v1),(u2,v2) ...(uk,vk) with the smallest sums.

Example 1:

Given nums1 = [1,7,11], nums2 = [2,4,6], k = 3

Return: [1,2],[1,4],[1,6]

The first 3 pairs are returned from the sequence: [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

Solution:

from heapq import heappop, heappush

class Solution:
def kSmallestPairs(self, nums1, nums2, k):
"""
:type nums1: List[int]
:type nums2: List[int]
:type k: int
:rtype: List[List[int]]
"""
solution = []
min_heap = []

# if nums1 or nums2 is empty or k is 0, we're done
if not nums1 or not nums2 or not k:
return solution

# first initialize min_heap with all
# (nums1[0..n], nums2[0]) pairs with
# (sum of pair, (nums1[0..n], nums2[0]), index of nums2)
for value in nums1:
heappush(min_heap, (value+nums2[0], (value, nums2[0]), 0))

while k and min_heap:
curr_pair = heappop(min_heap)
solution.append(curr_pair[1])
nums2_idx = curr_pair[2]
k -= 1
# if we haven't exhausted all (nums1[curr], nums2[0..n])
# pairs, offer pair (nums1[curr], nums2[curr+1]) to min_heap
if curr_pair[2] == len(nums2)-1: continue

heappush(min_heap, (curr_pair[1][0]+nums2[nums2_idx+1], (curr_pair[1][0],
nums2[nums2_idx+1]), nums2_idx+1))

return solution

1. There's no need for the special case not k, because that is already handled by the while k in the main loop.

2. In the initial loop over nums1 the expression nums2[0] gets computed twice. This could be avoided by storing the result in a local variable:

value2 = nums2[0]
heappush(min_heap, (value + value2, (value, value2), 0))

3. In the main loop there are some complicated expressions, culminating in:

heappush(min_heap, (curr_pair[1][0]+nums2[nums2_idx+1], (curr_pair[1][0],
nums2[nums2_idx+1]), nums2_idx+1))

which I found hard to understand. Complex expressions can be made clearer by giving names to the subexpressions. In particular, we can use tuple assignment to give names to all the elements of the tuple:

_, pair, j = heappop(min_heap)
value1, _ = pair

The reason for writing the tuple assignment value1, _ = pair instead of the lookup value1 = pair[0] is that the tuple assignment shows the reader that the pair has exactly two elements. (And if it doesn't then Python will raise "ValueError: not enough values to unpack" or "ValueError: too many values to unpack", so we get some checking too).

4. Now the heappush call looks like this:

heappush(min_heap, (value1 + nums2[j + 1], (value1, nums2[j + 1]), j + 1)

Here the expression nums2[j + 1] gets computed twice. This could be avoided by using a local variable:

value2 = nums2[j + 1]
heappush(min_heap, (value1 + value2, (value1, value2), j + 1)

5. Now, it ought to strike you that there is a strong similarity between the revised code in §1 and §4 above. The duplication could be avoided by defining a local function, like this:

solution = []
heap = []

# Add the pair (value1, nums2[j]) to the heap if possible.
if j < len(nums2):
value2 = nums2[j]
heappush(heap, (value1 + value2, (value1, value2), j))

for value1 in nums1:

while k and heap:
k -= 1
_, pair, j = curr_pair = heappop(heap)
solution.append(pair)
value1, _ = pair

return solution

Note that in this version of the code there is no longer any need for the special cases not num1 and not nums2. If nums1 is empty, then there will be no iterations for for value1 in nums1. If nums2 is empty, then j < len(nums2) will always be false, and so nothing will be added to the heap. Either way, there will be no iterations of the main loop and so the solution will be empty as required.

6. The revised code in §5 above always takes at least as many steps as there are elements in nums1. But this is wasteful in many cases. Consider something like:

kSmallestPairs(list(range(1000000)), [1, 2, 3], 1)

Since k=1, then result should be the single pair [(0, 1)]. But the initialization loop runs over all the million elements of nums1.

This could be avoided by initializing the heap with the single pair (nums1[0], nums2[0]) since we know that this is the pair with the smallest sum. And then when we pop a pair (nums1[i], nums2[j]) from the heap, we have to add two new pairs to the heap: that is, (nums1[i + 1], nums2[j]) and (nums1[i], nums2[j + 1]), as either of these pairs might be next in order after the pair we just processed.

However, we have to be careful to add each pair just once — after processing (nums1[1], nums2[0]) and (nums1[0], nums2[1]) we must not add the pair (nums1[1], nums2[1]) twice. This can be avoided by keeping a set of all the pairs we have added to the heap.

solution = []
heap = []     # Min-heap of (nums1[i] + nums2[j], i, j)
added = set() # Set of indexes (i, j) that have been added to heap.

# Add (nums1[i] + nums2[j], i, j) to the heap if possible.
if i < len(nums1) and j < len(nums2) and (i, j) not in added:


text:
Free Version
Easy

# Alternating Power Series

SVCALC-NYUB8Z

For which of the following values of $p$ is the following series convergent?

$$\sum_{n=1}^\infty \frac{(-1)^n}{n^p}$$

Select ALL that apply.

A

$p=2$

B

$p=1$

C

$p=\cfrac{1}{2}$

D

$p=0$

E

$p=-\cfrac{1}{2}$


text:
# 数据结构---排序

### 输入样例:

4 1 2 4 -1
4 7 6 -2 -3

### 输出样例:

43

#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1000002;
int arr1[MAXN], arr2[MAXN];
int main()
{
int n, m;
scanf("%d", &n);
for(int i = 0; i < n; ++i)
scanf("%d", &arr1[i]);
scanf("%d", &m);
for(int i = 0; i < n; ++i)
scanf("%d", &arr2[i]);
sort(arr1, arr1 + n, greater<int>());
sort(arr2, arr2 + n, greater<int>());
int f = 0, e1 = n - 1, e2 = n - 1;
long long ans = 0;
while(f < n && arr1[f] > 0 && arr2[f] > 0)
ans += arr1[f] * arr2[f], f++;
while(e1 >= f && arr1[e1] < 0 && arr2[e2] < 0)
ans += arr1[e1] * arr2[e2], e1--, e2--;
printf("%lld\n", ans);
return 0;
}

### 输入样例:

4 4
51 100 1000
36 110 300
6 14 32
5 18 40
0 1 2 3

### 输出样例:

1:1 1:2 1:3 1:4

#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 225;
struct infi{
int ID;
int g, m, p;
double avgg, avgm;
int r[4];
}national[MAXN];
struct ans{
int r, cal;
}Ans[MAXN];
bool cmp1(struct infi a, struct infi b);
bool cmp2(struct infi a, struct infi b);
bool cmp3(struct infi a, struct infi b);
bool cmp4(struct infi a, struct infi b);
int main()
{
int n, m;
int nation;
scanf("%d%d", &n, &m);
for(int i = 0; i < n; ++i)
{
scanf("%d%d%d",&national[i].g, &national[i].m, &national[i].p);
national[i].avgg = 1.0 * national[i].g / national[i].p;
national[i].avgm = 1.0 * national[i].m / national[i].p;
national[i].ID = i;
}
sort(national, national + n, cmp1);
int tmp = national[0].g, r0 = 2, r = 1;
national[0].r[0] = 1;
for(int i = 1; i < n; ++i)
{
if(tmp != national[i].g) r = r0, tmp = national[i].g;
national[i].r[0] = r, r0++;
}
sort(national, national + n, cmp2);
tmp = national[0].m, r0 = 2, r = 1;
national[0].r[1] = 1;
for(int i = 1; i < n; ++i)
{
if(tmp != national[i].m) r = r0, tmp = national[i].m;
national[i].r[1] = r, r0++;
}
sort(national, national + n, cmp3);
double tmpavg = national[0].avgg;
r0 = 2, r = 1, national[0].r[2] = 1;
for(int i = 1; i < n; ++i)
{
if(tmpavg != national[i].avgg) r = r0, tmpavg = national[i].avgg;
national[i].r[2] = r, r0++;
}
sort(national, national + n, cmp4);
tmpavg = national[0].avgm;
r0 = 2, r = 1, national[0].r[3] = 1;
for(int i = 1; i < n; ++i)
{
if(tmpavg != national[i].avgm) r = r0, tmpavg = national[i].avgm;
national[i].r[3] = r, r0++;
}
for(int i = 0; i < m; ++i)
{
scanf("%d", &nation);
int index = 0, tmpr = MAXN;
for(int j = 0; j < n; ++j)
{
if(national[j].ID == nation)
{
nation = j;
break;
}
}
for(int j = 0; j < 4; ++ j)
if(tmpr > national[nation].r[j]) index = j, tmpr = national[nation].r[j];
Ans[i].r = tmpr;
if(index == 0) Ans[i].cal = 1;
else if(index == 1) Ans[i].cal = 2;
else if(index == 2) Ans[i].cal = 3;
else if(index == 3) Ans[i].cal = 4;
}
for(int i = 0; i < m; ++i)
{
if(i) printf(" ");
printf("%d:%d", Ans[i].r, Ans[i].cal);
}
return 0;
}
bool cmp1(struct infi a, struct infi b)
{
return a.g > b.g;
}
bool cmp2(struct infi a, struct infi b)
{
return a.m > b.m;
}
bool cmp3(struct infi a, struct infi b)
{
return a.avgg > b.avgg;
}
bool cmp4(struct infi a, struct infi b)
{
return a.avgm > b.avgm;
}

2015年胡润研究院的调查显示，截至2014年9月，个人资产在600万元以上高净值人群达290万人。假设给出N个人的个人资产值，请快速找出资产排前M位的大富翁。

### 输入样例:

8 3
8 12 7 3 20 9 5 18

### 输出样例:

20 18 12

#include <iostream>
#include <stdio.h>
using namespace std;
const int MAXN = 1000002;
int arr[MAXN];
void Swap(int &a, int &b);
int main()
{
int n, m;
cin>>n>>m;
m = m < n ? m : n;
for(int i = 0; i < n; ++i)
scanf("%d",&arr[i]);
for(int i = 0; i < m; ++i)
{
for(int j = n - 1; j > i; --j)
{
if(arr[j] > arr[j - 1])
Swap(arr[j], arr[j - 1]);
}
}
for(int i = 0; i < m; ++i)
{
if(i) printf(" ");
printf("%d",arr[i]);
}
return 0;
}
void Swap(int &a, int &b)
{
int tmp = a;
a = b;
b = tmp;
}

PAT排名汇总   (25分)

### 输入样例:

2
5
1234567890001 95
1234567890005 100
1234567890003 95
1234567890002 77
1234567890004 85
4
1234567890013 65
1234567890011 25
1234567890014 100
1234567890012 85

### 输出样例:

9
1234567890005 1 1 1
1234567890014 1 2 1
1234567890001 3 1 2
1234567890003 3 1 2
1234567890004 5 1 4
1234567890012 5 2 2
1234567890002 7 1 5
1234567890013 8 2 3
1234567890011 9 2 4

1）首先，在一个考场的按要求排序

2）之后，将一个考场的排序与各个考场合并过的信息排序

#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
const int MAXN = 30003;
struct infi{
char ID[15];
int plant, score;
int r;
bool operator <(const struct infi p) const{
if(score != p.score)
return score > p.score;
else
return strcmp(ID, p.ID) < 0;
}
}peo[MAXN], tmp[303], tmpMer[MAXN];
int Merge(int l, int m);
int main()
{
int n, m, l = 0;
scanf("%d", &n);
for(int plant = 1; plant <= n; ++plant)
{
scanf("%d", &m);
for(int i = 0; i < m; ++i)
{
scanf("%s %d", tmp[i].ID, &tmp[i].score);
tmp[i].plant = plant;
} //以上读入信息
sort(tmp, tmp + m);
int r0 = 1, r = 1;
int s = tmp[0].score;
for(int i = 0; i < m; ++i)
{
if(tmp[i].score != s) r = r0, s = tmp[i].score;
tmp[i].r = r, r0++;
} //以上是对考场排序
l = Merge(l, m); //此处是合并到本次考试中
}
int r0 = 1, r = 1;
int s = peo[0].score;
printf("%d\n", l);
for(int i = 0; i < l; ++i)
{
if(peo[i].score != s) r = r0, s = peo[i].score;
printf("%s %d %d %d\n", peo[i].ID, r, peo[i].plant, peo[i].r);
r0++;
}
return 0;
}
int Merge(int l, int m)
{
int s1 = 0, s2 = 0, index = 0;
while(s1 < l && s2 < m)
{
if(peo[s1].score > tmp[s2].score)
{
tmpMer[index] = peo[s1];
s1++, index++;
}
else if(peo[s1].score < tmp[s2].score)
{
tmpMer[index] = tmp[s2];
s2++, index++;
}
else
{
if(strcmp(peo[s1].ID, tmp[s2].ID) < 0)
tmpMer[index] = peo[s1], s1++, index++;
else tmpMer[index] = tmp[s2], s2++, index++;
}
}
while(s1 < l)
{
tmpMer[index] = peo[s1];
s1++, index++;
}
while(s2 < m)
{
tmpMer[index] = tmp[s2];
s2++, index++;
}
for(int i = 0; i < l + m; ++i)
{
peo[i] = tmpMer[i];
}
return l + m;
}

PAT Judge   (25分)

The ranklist of PAT is generated from the status list, which shows the scores of the submittions. This time you are supposed to generate the ranklist for PAT.

### Input Specification:

Each input file contains one test case. For each case, the first line contains 3 positive integers,NN (≤104\le 10^4), the total number of users, KK (≤5\le 5), the total number of problems, and MM (≤105\le 10^5), the total number of submittions. It is then assumed that the user id's are 5-digit numbers from 00001 toNN, and the problem id's are from 1 to KK. The next line contains KK positive integers p[i] (i=1, ..., KK), where p[i] corresponds to the full mark of the i-th problem. Then MM lines follow, each gives the information of a submittion in the following format:

user_id problem_id partial_score_obtained

where partial_score_obtained is either −1-1 if the submittion cannot even pass the compiler, or is an integer in the range [0,p[problem_id]]. All the numbers in a line are separated by a space.

### Output Specification:

For each test case, you are supposed to output the ranklist in the following format:

rank user_id total_score s[1] ... s[K]

where rank is calculated according to the total_score, and all the users with the sametotal_score obtain the samerank; and s[i] is the partial score obtained for thei-th problem. If a user has never submitted a solution for a problem, then "-" must be printed at the corresponding position. If a user has submitted several solutions to solve one problem, then the highest score will be counted.

The ranklist must be printed in non-decreasing order of the ranks. For those who have the same rank, users must be sorted in nonincreasing order according to the number of perfectly solved problems. And if there is still a tie, then they must be printed in increasing order of their id's. For those who has never submitted any solution that can pass the compiler, or has never submitted any solution, they must NOT be shown on the ranklist. It is guaranteed that at least one user can be shown on the ranklist.

### Sample Input:

7 4 20
20 25 25 30
00002 2 12
00007 4 17
00005 1 19
00007 2 25
00005 1 20
00002 2 2
00005 1 15
00001 1 18
00004 3 25
00002 2 25
00005 3 22
00006 4 -1
00001 2 18
00002 1 20
00004 1 15
00002 4 18
00001 3 4
00001 4 2
00005 2 -1
00004 2 0

### Sample Output:

1 00002 63 20 25 - 18
2 00005 42 20 0 22 -
2 00007 42 - 25 - 17
2 00001 42 18 18 4 2
5 00004 40 15 0 25 -

#include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;
const int MAXNP = 10002;
const int MAXNS = 6;
struct infi{
int ID;
int total, solve;
int Pid[MAXNS];
bool Psol[MAXNS], summit;
bool operator <(const struct infi s1) const{
bool order = true;
if(total != s1.total) order = total > s1.total;
else if(solve != s1.solve) order = solve > s1.solve;
else order = ID < s1.ID;
return order;
}
}stu[MAXNP]; //定义每个考生的信息，其中的成员分别存储考号，总分，解题数，每一题得分，每题的提交情况，是否提交
int Score[MAXNS]; //每题的分数
int main( )
{
int n, k, m;
int id, pid, sco, index = 1, rank = 1;
scanf("%d%d%d", &n, &k, &m);
for(int i = 0; i <= n; ++i)
{
stu[i].ID = i;
stu[i].total = stu[i].solve = 0;
stu[i].summit = false;
for(int j = 0; j <= k; ++j)
stu[i].Pid[j] = -2, stu[i].Psol[j] = false;
}
for(int i = 1; i <= k; ++i)
scanf("%d",&Score[i]);
for(int i = 0; i < m; ++i)
{
scanf("%d%d%d", &id, &pid, &sco);
if(stu[id].Pid[pid] < sco) 如果该考生的某题过去分数少于现在得分，则更新（注意题中编译出错的情况）
{
if(sco == Score[pid]) stu[id].solve++; //表示解决此题
if(sco == -1) sco = 0; //编译出错
stu[id].Pid[pid] = sco; //更新分数
if(!stu[id].Psol[pid]) stu[id].Psol[pid] = true; //此题是否提交过
stu[id].summit = true; //该考生本次考试提交过代码
}
}
for(int i = 1; i <= n; ++i) //得到总分
{
for (int j = 1; j <= k; ++j)
if(stu[i].Psol[j])
stu[i].total += stu[i].Pid[j];
}
sort(stu + 1, stu + n + 1);
sco = stu[1].total;
for(int i = 1; i <= n && stu[i].summit; ++i) //输出
{
if(sco != stu[i].total) rank = index;
index++;
printf("%d %05d %d", rank, stu[i].ID, stu[i].total);
for(int j = 1; j <= k; ++j)
if(stu[i].Psol[j]) printf(" %d", stu[i].Pid[j]);
else printf(" -");
printf("\n");
sco = stu[i].total;
}
return 0;
}

Insert or Merge   (25分)

According to Wikipedia:

Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.

Merge sort works as follows: Divide the unsorted list into N sublists, each containing 1 element (a list of 1 element is considered sorted). Then repeatedly merge two adjacent sublists to produce new sorted sublists until there is only 1 sublist remaining.

Now given the initial sequence of integers, together with a sequence which is a result of several iterations of some sorting method, can you tell which sorting method we are using?

### Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integerNN (≤100\le 100). Then in the next line, NN integers are given as the initial sequence. The last line contains the partially sorted sequence of theNN numbers. It is assumed that the target sequence is always ascending. All the numbers in a line are separated by a space.

### Output Specification:

For each test case, print in the first line either "Insertion Sort" or "Merge Sort" to indicate the method used to obtain the partial result. Then run this method for one more iteration and output in the second line the resuling sequence. It is guaranteed that the answer is unique for each test case. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.

### Sample Input 1:

10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0

### Sample Output 1:

Insertion Sort
1 2 3 5 7 8 9 4 6 0

### Sample Input 2:

10
3 1 2 8 7 5 9 4 0 6
1 3 2 8 5 7 4 9 0 6

### Sample Output 2:

Merge Sort
1 2 3 8 4 5 7 9 0 6

#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
const int MAXN = 102;
int num1[MAXN], num2[MAXN];
bool Merge(int n);
int main()
{
int n;
cin>>n;
for(int i = 0; i < n; ++i)
cin>>num1[i];
for(int i = 0; i < n; ++i)
cin>>num2[i];
if(Merge(n))
{
cout<<"Merge Sort"<<endl;
for(int i = 0; i < n - 1; ++i)
cout<<num1[i]<<' ';
cout<<num1[n-1]<<endl;
}
else
{
cout<<"Insertion Sort"<<endl;
for(int i = 1; i < n; ++i)
{
if(num2[i - 1] > num2[i])
{
int tmp = num2[i];
for(; i >0 && tmp < num2[i - 1]; --i)
num2[i] = num2[i - 1];
num2[i] = tmp;
break;
}
}
for(int i = 0; i < n - 1; ++i)
cout<<num2[i]<<' ';
cout<<num2[n - 1]<<endl;
}
return 0;
}
bool Merge(int n)
{
int i;
bool isMerge = false;
for(int setp = 1; true; ++setp)
{
int len = 1 << setp;
int f = 0, e = len;
if(e > n)
{
sort(num1, num1 + n);
break;
}
while(f < n)
{
sort(num1 + f,num1 + e);
f += len, e += len;
if(e > n) e = n;
}
if(isMerge) break;
for(i = 0; i < n; ++i)
if(num1[i] != num2[i]) break;
if(i >= n) isMerge = true;
}
return isMerge;
}

Insertion or Heap Sort   (25分)

According to Wikipedia:

Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.

Heap sort divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region. it involves the use of a heap data structure rather than a linear-time search to find the maximum.

Now given the initial sequence of integers, together with a sequence which is a result of several iterations of some sorting method, can you tell which sorting method we are using?

### Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integerNN (≤100\le 100). Then in the next line, NN integers are given as the initial sequence. The last line contains the partially sorted sequence of theNN numbers. It is assumed that the target sequence is always ascending. All the numbers in a line are separated by a space.

### Output Specification:

For each test case, print in the first line either "Insertion Sort" or "Heap Sort" to indicate the method used to obtain the partial result. Then run this method for one more iteration and output in the second line the resuling sequence. It is guaranteed that the answer is unique for each test case. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.

### Sample Input 1:

10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0

### Sample Output 1:

Insertion Sort
1 2 3 5 7 8 9 4 6 0

### Sample Input 2:

10
3 1 2 8 7 5 9 4 6 0
6 4 5 1 0 3 2 7 8 9

### Sample Output 2:

Heap Sort
5 4 3 1 0 2 6 7 8 9

#include <iostream>
#include <stdio.h>
using namespace std;
const int MAXN = 102;
int num1[MAXN], num2[MAXN];
bool HeapSort(int n);
void Swap(int &a, int &b);
int main()
{
int n;
cin>>n;
for(int i = 1; i <= n; ++i)
cin>>num1[i];
for(int i = 1; i <= n; ++i)
cin>>num2[i];
if(HeapSort(n))
{
cout<<"Heap Sort"<<endl;
for(int i = 1; i < n; ++i)
cout<<num1[i]<<' ';
cout<<num1[n]<<endl;
}
else
{
cout<<"Insertion Sort"<<endl;
for(int i = 2; i <= n; ++i)
{
if(num2[i - 1] > num2[i])
{
int tmp = num2[i];
for(; i >1 && tmp < num2[i - 1]; --i)
num2[i] = num2[i - 1];
num2[i] = tmp;
break;
}
}
for(int i = 1; i < n; ++i)
cout<<num2[i]<<' ';
cout<<num2[n]<<endl;
}
return 0;
}
bool HeapSort(int n)
{
int i;
bool isHeap = false;
for(int index = n >> 1; index > 0; --index)
while(n > 1)
{
Swap(num1[1], num1[n]);
n--;
if(isHeap) break;
for(i = 1; i <= n; ++i)
if(num1[i] != num2[i]) break;
if(i > n) isHeap = true;
}
return isHeap;
}
{
while((index << 1) <= n)
{
int i = index;
if(num1[index << 1] > num1[i])
{
int tmp = num1[index << 1];
index <<= 1;
if(index + 1 <= n && num1[index + 1] > tmp)
index++;
Swap(num1[index], num1[i]);
}
else if((index << 1) + 1 <= n && num1[(index << 1) + 1] > num1[index])
{
Swap(num1[index], num1[(index << 1) + 1]);
index = (index << 1) + 1;
}
else
{
break;
}
}
}
void Swap(int &a, int &b)
{
int tmp = a;
a = b;
b = tmp;
}

Sort with Swap(0, i)   (25分)

Given any permutation of the numbers {0, 1, 2,..., N−1N-1}, it is easy to sort them in increasing order. But what if Swap(0, *) is the ONLY operation that is allowed to use? For example, to sort {4, 0, 2, 1, 3} we may apply the swap operations in the following way:

Swap(0, 1) => {4, 1, 2, 0, 3}
Swap(0, 3) => {4, 1, 2, 3, 0}
Swap(0, 4) => {0, 1, 2, 3, 4}

Now you are asked to find the minimum number of swaps need to sort the given permutation of the firstNN nonnegative integers.

### Input Specification:

Each input file contains one test case, which gives a positive NN (≤105\le 10^5) followed by a permutation sequence of {0, 1, ..., N−1N-1}. All the numbers in a line are separated by a space.

### Output Specification:

For each case, simply print in a line the minimum number of swaps need to sort the given permutation.

### Sample Input:

10
3 5 7 2 6 4 9 0 8 1

### Sample Output:

9

#include <iostream>
#include <stdio.h>
using namespace std;
const int MAXN = 100002;
int num[MAXN], Index[MAXN];
void Swap(int &a, int &b);
int main()
{
int n;
int cnt = 0;
scanf("%d", &n);
for(int i = 0; i < n; ++i)
{
scanf("%d", &num[i]); //数字序列
Index[num[i]] = i; //数字所在序列的下标
}
for(int i = 0;i < n; ++i)
{
while(Index[0] != 0) //下标为零的位置不是零，则交换
{
int index = Index[Index[0]]; //在下标为零的数字的位置
Swap(num[index], num[Index[0]]);//数字和零交换到正确的位置
Index[Index[0]] = Index[0]; //并且更新数字在序列中的位置
Index[0] = index;
cnt++; //交换一次
}
for(; i < n && num[i] == i; ++i); //寻找是否还有使序列无序的元素
if(i < n) //如果有，则与零交换
{
Swap(num[0], num[i]);
Index[num[0]] = 0;
Index[0] = i;
cnt++;
}
}
printf("%d\n",cnt);
return 0;
}
void Swap(int &a, int &b)
{
int tmp = a;
a = b;
b = tmp;
}

• 本文已收录于以下专栏：

举报原因： 您举报文章：数据结构---排序 色情 政治 抄袭 广告 招聘 骂人 其他 (最多只允许输入30个字)


text:
# Probability of winning exactly one...

• Oct 11th 2010, 01:04 PM
Iceflash234
Probability of winning exactly one...
Given there were 50 tickets sold, you bought 5, and there are three prizes (1st, 2nd, and 3rd), what is the probability of winning exactly one prize.

I don't stand how to show the probability of an "exactly one" scenario. I know how to find the probability of "at least" or "none".

Help is greatly appreciated.
• Oct 11th 2010, 01:10 PM
Plato
I see that you have over twenty-five postings.
By now you should understand that this is not a homework service
So you need to either post some of your work on a problem or explain what you do not understand about the question.
• Oct 11th 2010, 01:13 PM
Iceflash234
I don't stand how to show the probability of an "exactly one" scenario. I know how to find the probability of "at least" or "none".
• Oct 11th 2010, 01:31 PM
Plato
There are $\dbinom{3}{1}\dbinom{47}{4}$ ways to win exactly one prize with five tickets.
• Oct 11th 2010, 02:27 PM
Iceflash234
Quote:

Originally Posted by Plato
There are $\dbinom{3}{1}\dbinom{47}{4}$ ways to win exactly one prize with five tickets.

So the probability of getting exactly one would be $\frac{1}{\dbinom{3}{1}\dbinom{47}{4}}$ ?

That makes sense. Thanks! I appreciate it.
• Oct 11th 2010, 02:32 PM
Plato
Good grief. NO! This totally wrong.
• Oct 11th 2010, 02:43 PM
Iceflash234
Quote:

Originally Posted by Plato
Good grief. NO! This totally wrong.

Wait what? How? $\dbinom{3}{1}\dbinom{47}{4}$ is the number of ways to win exactly one with 5 tickets.

Oh wait a minute, I need to figure out the number of total overall possible winning combinations and then divide the number of ways to win by the total number of winning combinations. But regardless of whether I do 50C3 or 50P3, both of which are smaller that the above combinations so they wouldn't work. Now I'm confused.
• Oct 11th 2010, 03:17 PM
Plato
The answer is $\dfrac{\binom{3}{1}\binom{47}{4}}{\binom{50}{5}}$


text:
OpenGraph DrawingFramework

v. 2022.02 (Dogwood)

ogdf::LCA Class Reference

Implements the <O(n log n), O(1)>-time "sparse table" algorithm by Bender and Farach-Colton to compute lowest common ancestors (LCAs) in arborescences (not arbitrary directed acyclic graphs). More...

#include <ogdf/tree/LCA.h>

Public Member Functions

LCA (const Graph &G, node root=nullptr)
Builds the LCA data structure for an arborescence. More...

node call (node u, node v) const
Returns the LCA of two nodes u and v. More...

int level (node v) const
Returns the level of a node. The level of the root is 0. More...

Private Member Functions

void buildTable ()
Fills the O(n log n)-space matrix with auxiliary data the LCA values can be computed from. More...

void dfs (const Graph &G, node root)
Performs an Euler tour (actually a DFS with virtual back-edges) through the underlying tree and fills Euler tour and Level arrays. More...

int rmq (int u, int v) const
Returns the internal index pointing to the LCA between two nodes u and v. More...

const int & sparseTable (int i, int j) const
Access the sparse table at [i, j]. More...

int & sparseTable (int i, int j)

Private Attributes

Array< nodem_euler
Euler[i] is i-th node visited in Euler Tour. More...

const int m_len
length of the RMQ array (always 2 m_n - 1) More...

Array< int > m_level
L[i] is distance of node E[i] from root. More...

const int m_n
number of nodes in graph More...

const int m_rangeJ
always floor(log(m_len)) (size of a row in the table) More...

NodeArray< int > m_representative
Euler[Representative[v]] = v. More...

const node m_root
the root of the tree More...

Array< int > m_table
preprocessed M[i,j] array More...

Detailed Description

Implements the <O(n log n), O(1)>-time "sparse table" algorithm by Bender and Farach-Colton to compute lowest common ancestors (LCAs) in arborescences (not arbitrary directed acyclic graphs).

This implementation is based on:

(M. Bender, M. Farach-Colton, The LCA problem revisited, LATIN '00, volume 1776 of LNCS, pages 88-94, Springer, 2000)

Definition at line 52 of file LCA.h.

◆ LCA()

 ogdf::LCA::LCA ( const Graph & G, node root = nullptr )
explicit

Builds the LCA data structure for an arborescence.

If root is not provided, it is computed in additional O(n) time.

Parameters
 G an arborescence root optional root of the arborescence
Precondition
Each node in G is reachable from the root via a unique directed path, that is, G is an arborescence.

◆ buildTable()

 void ogdf::LCA::buildTable ( )
private

Fills the O(n log n)-space matrix with auxiliary data the LCA values can be computed from.

◆ call()

 node ogdf::LCA::call ( node u, node v ) const

Returns the LCA of two nodes u and v.

If u and v are the same node, u itself is defined to be the LCA, not its father.

◆ dfs()

 void ogdf::LCA::dfs ( const Graph & G, node root )
private

Performs an Euler tour (actually a DFS with virtual back-edges) through the underlying tree and fills Euler tour and Level arrays.

◆ level()

 int ogdf::LCA::level ( node v ) const
inline

Returns the level of a node. The level of the root is 0.

Definition at line 74 of file LCA.h.

◆ rmq()

 int ogdf::LCA::rmq ( int u, int v ) const
private

Returns the internal index pointing to the LCA between two nodes u and v.

Returns
Internal index pointing to LCA

◆ sparseTable() [1/2]

 int& ogdf::LCA::sparseTable ( int i, int j )
inlineprivate

Definition at line 111 of file LCA.h.

◆ sparseTable() [2/2]

 const int& ogdf::LCA::sparseTable ( int i, int j ) const
inlineprivate

Access the sparse table at [i, j].

Precondition
0 <= i < m_len and 1 <= j <= m_rangeJ

Definition at line 107 of file LCA.h.

◆ m_euler

 Array ogdf::LCA::m_euler
private

Euler[i] is i-th node visited in Euler Tour.

Definition at line 84 of file LCA.h.

◆ m_len

 const int ogdf::LCA::m_len
private

length of the RMQ array (always 2 m_n - 1)

Definition at line 82 of file LCA.h.

◆ m_level

 Array ogdf::LCA::m_level
private

L[i] is distance of node E[i] from root.

Definition at line 86 of file LCA.h.

◆ m_n

 const int ogdf::LCA::m_n
private

number of nodes in graph

Definition at line 81 of file LCA.h.

◆ m_rangeJ

 const int ogdf::LCA::m_rangeJ
private

always floor(log(m_len)) (size of a row in the table)

Definition at line 83 of file LCA.h.

◆ m_representative

 NodeArray ogdf::LCA::m_representative
private

Euler[Representative[v]] = v.

Definition at line 85 of file LCA.h.

◆ m_root

 const node ogdf::LCA::m_root
private

the root of the tree

Definition at line 80 of file LCA.h.

◆ m_table

 Array ogdf::LCA::m_table
private

preprocessed M[i,j] array

Definition at line 87 of file LCA.h.

The documentation for this class was generated from the following file:
• include/ogdf/tree/LCA.h


text:
Reaktoro  v2.6.0 A unified framework for modeling chemically reactive systems
ChemicalPropsPhaseBaseData< TypeOp > Struct Template Reference

The base type for primary chemical property data of a phase from which others are computed. More...

#include <ChemicalPropsPhase.hpp>

## Public Member Functions

template<template< typename > typename OtherTypeOp>
auto operator= (const ChemicalPropsPhaseBaseData< OtherTypeOp > &other)
Assign a ChemicalPropsPhaseBaseData object to this.

template<template< typename > typename OtherTypeOp>
operator ChemicalPropsPhaseBaseData< OtherTypeOp > ()
Convert this ChemicalPropsPhaseBaseData object into another.

template<template< typename > typename OtherTypeOp>
operator ChemicalPropsPhaseBaseData< OtherTypeOp > () const
Convert this ChemicalPropsPhaseBaseData object into another.

auto operator= (const ArrayStream< real > &array)
Assign the given array data to this ChemicalPropsPhaseBaseData object.

operator ArrayStream< real > () const
Convert this ChemicalPropsPhaseBaseData object into an array.

## Public Attributes

TypeOp< realT
The temperature of the phase (in K).

TypeOp< realP
The pressure of the phase (in Pa).

TypeOp< ArrayXrn
The amounts of each species in the phase (in mol).

TypeOp< realnsum
The amount of the phase as the sum of species amounts (in mol).

TypeOp< realmsum
The mass of the phase as the sum of species masses (in kg).

TypeOp< ArrayXrx
The mole fractions of the species in the phase (in mol/mol).

TypeOp< ArrayXrG0
The standard molar Gibbs energies of formation of the species in the phase (in J/mol)

TypeOp< ArrayXrH0
The standard molar enthalpies of formation of the species in the phase (in J/mol)

TypeOp< ArrayXrV0
The standard molar volumes of the species in the phase (in m³/mol)

TypeOp< ArrayXrVT0
The temperature derivative of the standard molar volumes of the species in the phase (in m³/(mol·K)).

TypeOp< ArrayXrVP0
The pressure derivative of the standard molar volumes of the species in the phase (in m³/(mol·Pa)).

TypeOp< ArrayXrCp0
The standard molar isobaric heat capacities of the species in the phase (in J/(mol·K))

TypeOp< realVx
The corrective molar volume of the phase (in m³/mol).

TypeOp< realVxT
The temperature derivative of the corrective molar volume at constant pressure (in m³/(mol·K)).

TypeOp< realVxP
The pressure derivative of the corrective molar volume at constant temperature (in m³/(mol·Pa)).

TypeOp< realGx
The corrective molar Gibbs energy of the phase (in units of J/mol).

TypeOp< realHx
The corrective molar enthalpy of the phase (in units of J/mol).

TypeOp< realCpx
The corrective molar isobaric heat capacity of the phase (in units of J/(mol·K)).

TypeOp< ArrayXrln_g
The activity coefficients (natural log) of the species in the phase.

TypeOp< ArrayXrln_a
The activities (natural log) of the species in the phase.

TypeOp< ArrayXru
The chemical potentials of the species in the phase.

TypeOp< StateOfMattersom
The state of matter of the phase.

## Detailed Description

### template<template< typename > typename TypeOp> struct Reaktoro::ChemicalPropsPhaseBaseData< TypeOp >

The base type for primary chemical property data of a phase from which others are computed.

The documentation for this struct was generated from the following file:


text:
# Do massless particles really exist?

Here is a quick & simple answer until the professionals arrive. In the Standard Model, it is zero. This $< 1\cdot 10^{-18} \frac{\mathrm{eV}}{c^2}$ is an experimental upper limit (i.e. if it has a rest mass, because of physics beyond the Standard Model, it must be smaller than this value).

This value is very small, compared to the estimated rest mass of the neutrinos (which is of the order of some tenths of an $\mathrm{eV}$).

We can't measure to infinite precision; so even if a particle had in fact zero mass we couldn't experimentally measure it to the infinite precision needed to justify this; which is why certain amount of judgement is called for, and that judgement is made in the context of a theoretical framework.

The second point to make is that all particles with zero rest mass travel at the speed of light and they have momentum due to this motion.

As one answer has pointed out already such particles are gauge bosons which mediate the weak, strong & EM forces. For the EM force, this is the photon.

There are indeed massless particles.

As of 2015 there were two known massless particles (both gauge bosons): the photon (carrier of electromagnetism) and the gluon (carrier of the strong force). It should be noted, however, that gluons are never observed as free particles, since they are confined within hadrons.

Gravitons (if discovered) would be another massless particle.

Of course, it must be kept in mind that nothing can be measured to infinite precision. Because of this, we will never measure a photon's rest mass and find it to be zero. As our measurements get better and better, it will get closer to zero, but it will never quite get there.

Interestingly, according to this website, scientists are able to look at Coulomb's Law and other experimental results and place upper bounds on what the photon's rest mass can be measured as. The best upper bound to date is $1.07×10^{−27}$ atomic mass units. The equivalent of this is what you saw on the Wikipedia sidebar.


text:
TutorMe homepage
Subjects
PRICING
COURSES
Start Free Trial
Frank B.
Former University Math Professor for 10+ years
Tutor Satisfaction Guarantee
Pre-Calculus
TutorMe
Question:

Find the domain of the function: $$\frac{x^2 + 3x + 1}{x - 4}$$. Express using interval notation.

Frank B.

Rational functions have a domain of the entire real number set except for those values that make the denominator equal to zero. Solving for $$x - 4 = 0$$, we get $$x = 4$$. Thus the domain of the function is $$(- \infty, 4) \cup (4, \infty)$$.

Calculus
TutorMe
Question:

Find the derivative of $$x^3 + 3x^2 - 6x + 10.$$

Frank B.

Using the power rule for derivatives, the derivative is: $$3x^2 + 6x - 6.$$

Statistics
TutorMe
Question:

When would it be appropriate to use the Normal distribution as an approximation to the t-distribution?

Frank B.

Because the t-distribution converges to the Normal distribution with a high enough degrees of freedom, it's appropriate to use the Normal distribution approximation when the sample size is greater than 30.

Send a message explaining your
needs and Frank will reply soon.
Contact Frank
Ready now? Request a lesson.
Start Session
FAQs
What is a lesson?
A lesson is virtual lesson space on our platform where you and a tutor can communicate. You'll have the option to communicate using video/audio as well as text chat. You can also upload documents, edit papers in real time and use our cutting-edge virtual whiteboard.
How do I begin a lesson?
If the tutor is currently online, you can click the "Start Session" button above. If they are offline, you can always send them a message to schedule a lesson.
Who are TutorMe tutors?
Many of our tutors are current college students or recent graduates of top-tier universities like MIT, Harvard and USC. TutorMe has thousands of top-quality tutors available to work with you.


text:
# When does an unpaired test result in higher p-value than a paired test?

I determined some parameter in a group of subjects under two conditions, such that each subject was tested in both conditions. I want to know if the condition has an effect on the parameter. My design is obviously paired. However, previous experience with this experiment makes me believe that the subject's response is independent during each measurement. Thus, I assume that subjects are independent and not paired. Accordingly, I decide to analyze the data with an unpaired t-test. But out of curiosity, I also run a paired t-test, with the following results:

P value for the paired T-test is 0.08 (no difference). P value for the unpaired T-test is 0.04 (significant difference).

I am confused because I thought that a paired test should always give lower p-value (or equal in the worst case) than an unpaired test, by eliminating between-subject variability and increasing power.

Questions:

1) When can a paired test produce higher p-value that an unpaired test? What does my result mean in terms of sources of variation? It seems that pairing the subjects not only does not eliminate between-subject variability, but adds some kind of a new variability.

2) Can this result tell me something about my assumption that subjects are independent? Can it invalidate this assumption?

3) In summary, is it always a matter of choice to pair or not to pair subjects during analysis? Or is it formally incorrect to use an unpaired test when subjects are logically paired?

• "Eliminating between-subject variability" usually is impossible; surely you mean to refer to reducing that variability. But a reduction occurs only when the pairs are positively correlated--not when they are negatively correlated! – whuber Oct 29 '14 at 20:17
• @whuber, I might describe a paired t-test as analyzing 'scores conditional on the subject'. In that context it seems reasonable to me to say that the b-s variability has been eliminated--it's certainly still there in the data but not in the data as analyzed. Re: -cor, that seems to be the answer, why not make it official? – gung - Reinstate Monica Oct 29 '14 at 20:33
• @gung This terminology always makes me think for a minute: isn't "between-subjects" variability the component attributable to variation from one subject to another, while "within-subjects" is the component specific to each subject? Regardless, why would it be valid to suppose that either one can be eliminated altogether? I guess I don't understand the distinction you are making between being present "in the data" and being present in the "data as analyzed." BTW, correlation is not the entire story: it has to be balanced against the effect of degrees of freedom. – whuber Oct 29 '14 at 20:44

1. As @whuber says in the comment above, when the measures are negatively correlated, the p-value can be lower in the unpaired test than in the paired test. Here's an example where there is a difference:

library(MASS)
s  <- matrix(c(1, -0.8, -0.8, 1), 2)
df <- mvrnorm(n=100, mu=c(0, 0.3), Sigma=s, empirical=TRUE)
t.test(df[,1], df[, 2], paired=FALSE)
t.test(df[,1], df[, 2], paired=TRUE)

The first test (unpaired) gives p=0.035, the second gives p=0.117.

2. Yes, this is a design issue. This book chapter discusses it: Keren, G. (2014). Between-or within-subjects design: A methodological dilemma. A Handbook for Data Analysis in the Behaviorial Sciences: Volume 1: Methodological Issues Volume 2: Statistical Issues, 257, which you can read some of on Google books.

3. Hmmm... I'm not sure. I'd do a simulation to find out the effect on the type I error rate. How this affects your power is a separate issue that I haven't looked into here. Slight adaptation of my previous code:

paired   <- rep(NA, 1000)
unpaired <- rep(NA, 1000)
for(i in 1:1000){
df          <- mvrnorm(n=100, mu=c(0, 0), Sigma=s, empirical=FALSE)
unpaired[i] <- t.test(df[,1], df[, 2], paired=FALSE)$p.value paired[i] <- t.test(df[,1], df[, 2], paired=TRUE )$p.value
}

sum(paired < 0.05)
sum(unpaired < 0.05)

Result:

> sum(paired < 0.05)
[1] 46
> sum(unpaired < 0.05)
[1] 137

Well look at that. If you treat them as unpaired, your type I error rate rockets. You need to treat them as paired to get the right answer. I believe (it's a long time since I've read it) that this is one of the issues Keren talks about in that chapter. If you're going to have data that might be negative correlated (e.g. amount of soup and amount of burgers someone eats) you'll have more power with an unpaired design.

• I beg to disagree with your interpretation of my comment: for the p-values to be reversed, it is necessary for there to be negative covariance; but this is not sufficient. The negative covariance has to overcome the loss of degrees of freedom in the paired t-test. – whuber Oct 29 '14 at 21:05
• What should we make of your proposed answer to #1 in light of your proposed answer to #3? – gung - Reinstate Monica Oct 29 '14 at 21:26
• @JeremyMiles Thanks for the detailed answer. I read the chapter from the book, but I couldn't find a more or less direct answer to my question. The core of my question is "can you treat paired subjects as unpaired", while the chapter just compares true within-subject and between-subject designs in general. – Viktor Oct 31 '14 at 15:20
• Regarding your answer, let me just confirm if I understand it correctly. Your conclusions seems to be: 1) My results show that the measurements of one subject in two different conditions cannot be considered independent, because they are (negatively) correlated; 2) thus, paired test must be used, and provides "more true" measure of the treatment effect. Is that correct? – Viktor Oct 31 '14 at 15:21
• Yes, I think you need to treat them as paired. – Jeremy Miles Oct 31 '14 at 16:51


text:
# Law of Conservation of Energy

Energy is required for the evolution of life forms on earth. In Physics, it is defined as the capacity to do work. We know that energy exists in different forms in nature. You have learned about various forms of energy – heat, electrical, chemical, nuclear, etc. In this article, we will learn about the laws and principles which governs energy known as the law of conservation of energy.

## What is the Law of Conservation of Energy?

The law of conservation of energy states that energy can neither be created nor be destroyed. It may be transferred from one of its forms to the other. If you take all forms of energy into account, the total energy of an isolated system always remains constant.

So in an isolated system such as the universe, if there is a loss of energy in some part of it, there must be a gain of an equal amount of energy in some other part of the universe. Although this principle cannot be proved, there is no known example of a violation of the law of conservation of energy.

### Proof for Law of Conservation of Energy:

Considering the potential energy at the surface of the earth to be zero. Let us see an example of a fruit falling from a tree.

Consider a point A, which is at some height ‘H’ from the ground on the tree, the velocity of the fruit is zero hence potential energy is maximum there.

E = mgH ———- (1)

When the fruit is falling, its potential energy is decreasing and kinetic energy is increasing.

At point B, which is near the bottom of the tree, the fruit is falling freely under gravity and is at a height X from the ground, and it has a speed as it reaches point B. So, at this point it will have both kinetic and potential energy.

E = K.E + P.E

P.E = mgX ——— (2)

According to third equation of motion,

$v^{2 }= 2g(H – X)\\ \\ \Rightarrow \frac{1}{2}mv^{2}=\frac{1}{2}m.2g(H – X)\\ \\ \Rightarrow K.E=\frac{1}{2}m.2g(H – X) \\ \Rightarrow K.E=mg(H – X)$

K.E=mg(H-X)——– (3)

Using (1), (2) and (3)

E = mg(H – X) + mgX

E = mg(H – X + X)

E = mgH

Similarly, if we see the energy at point C which is at the bottom of the tree, it will come out to be mgH. We can see as the fruit is falling to the bottom and here, potential energy is getting converted into kinetic energy. So there must be a point where kinetic energy becomes equal to potential energy. Suppose we need to find that height ‘x’ from the ground. We know that at that point,

K.E = P.E

=> P.E = K.E = $\frac {E}{2}$ ——– (4)

E2 is the new energy

Where, E = mgH2

H2 is the new height.

As the body is at height X from the ground,

P.E = mgX ——— (5)

Using (4) and (5) we get,

$mgX=\frac{mgH}{2}\\ \\ \Rightarrow X=\frac{H}{2}$

H2 is referred to the new height

### Energy Conservation:

Energy conservation is not about limiting the use of resources which will finally run out all together. The ideal way of conservation would be reducing demand on a limited supply and enabling that supply to begin to rebuild itself. Many times the best way of doing this is to replace the energy used with an alternate.

### Examples:

In physics, most of the inventions rely on the fact that energy is conserved when it is transferred from one form to another. A number of electrical and mechanical devices operate solely on the law of conservation of energy. We will discuss a few examples here.

• In a torch, the chemical energy of the batteries is converted into electrical energy, which is converted into light and heat energy.
• In hydroelectric power plants, waterfalls on the turbines from a height. This, in turn, rotates the turbines and generates electricity. Hence, the potential energy of water is converted into the kinetic energy of the turbine, which is further converted into electrical energy.
• In a loudspeaker, electrical energy is converted into sound energy.
• In a microphone, sound energy is converted into electrical energy.
• In a generator, mechanical energy is converted into electrical energy.
• When fuels are burnt, chemical energy is converted into heat and light energy.
• Chemical energy from food is converted to thermal energy when it is broken down in the body and is used to keep it warm.

Stay tuned with Byju’s to learn more about the law of conservation of energy, heat energy and much more.

#### Practise This Question

A heavy particle is suspended by a string of length l. The particle is given a horizontal velocity v0. The string becomes slack at some angle and the particle proceeds on a parabola. Find the value of v0 if the particle passes through the point of suspension.