Contacts and Phone icons missing
Same happened to me on my NOTE 3, and what I found was I had inadvertently TURNED OFF the CONTACTS app. 

On Samsung phones go to Settings, General tab, Application Manager scroll to the last page labeled "TURNED OFF". Click on the app you need to turn on and select Turn On. 

That did it for me.