Dishwasher air gap problem
I'd like to thank everyone participating and up-voting. I went to home depot today and bought a new air gap. Upon a further inspection I found out that my air gap is missing a cover: a piece of plastic that routes the water coming from the DW into the drain.

Long story short, it somehow got popped out and my wife "saved" it by sticking into the kitchen drawer.