Does the velocity of the wave change even if the medium properties remain the same? I read that velocity of any type of wave solely depend on the properties of the medium. Though properties of the medium remains same, does the wave velocity change? If so, give me the example so that I can change my teaching.
 A: The other answers are fine for linear waves, but for nonlinear waves (solitons) the wave velocity can vary with wave amplitude.
A: Firstly, you need to acknowledge that Electromagnetic waves propogate through space as a wave but interact with matter as a particle (a photon). This is known as wave-particle duality and requires some basic knowledge of Quantum Mechanics. 
Considering Electromagnetic waves first:
A light wave enters matter, the light wave's electric field
causes charged particles in the matter to accelerate back and
forth. That's because an electric field exerts forces on charged
particles. The light wave gives up some of its energy to these charged
particles and is partially absorbed in the process. However, the
charged particles don't retain the light's energy very long. They are
accelerating and accelerating charged particles emit electromagnetic
waves. In fact, they reemit the very same light wave that they
absorbed moments earlier. Overall, the light wave is partially
absorbed and then reemitted by each electrically charged particle it
encounters, so that the light continues on its way as though nothing
had happened.
However, something has happened; the light wave has been delayed
ever so slightly. This absorption and re-emission process holds the
light wave back so that it travels at less than its full speed. If the
charged particles in the matter are few and far between, this slowing
effect is almost insignificant. But in dense materials such as glass
or diamond, the light wave can be slowed substantially.
Taking the extreme case where there is no media present whatsoever (a vacuum) then the speed of the electromagnetic waves is optimal, and equal to $c$.

If it is sound waves (longitudinal waves) however: 
We desire that the density of the medium is high. Why is this? If the atoms were widely spaced (low density) then the collisions between molecules of the medium would not be as frequent and as a result the wavelength will be larger and hence the speed of sound will be slower in such materials.
A: When it comes to waves the guitar string is a good analogy. Consider what happens as the string is tightened.  When plucked the wave in the string will have different velocities (even in a vacuum), wikipedia says: "The velocity of propagation of a wave in a string is proportional to the square root of the force of tension of the string (discovered by Vincenzo Galilei in the late 1500s) and inversely proportional to the square root of the linear density of the string".  What's interesting is the material is the same but the tension in it has increased.... 
