I really think the two-semester approach works well. The first semester covers basics and intuition and tasks students to implement and extend. The second semester formalizes the material and tasks students to analyze and design algorithms to solve various problems. The first can be taught to first-years and the second to second- or third-years depending on when it's standard to take discrete maths.