Schema-Based Instruction with Enumerative Combinatorics and Recursion to Develop Computer Engineering Students' Problem-Solving Skills

Learning and teaching problem solving is a hard task, no matter the domain. Computer Science is no exception. Recursion is a paradigm often used for problem solving, but it is non-intuitive and it is unnatural. Most second programming courses (CS2-level) for Computer Engineering students apply recursion to mathematical problems or basic recursive data structures with a limited focus on problem solving. Third programming courses (CS3-level) deal with search and optimization problems and they use recursion because of its ability, due to its backtracking mechanism, to explore the whole solution space. However, most of them do not rely on a systematic and well-formed approach to teaching this approach to problem solving. Our main contribution is to adopt schema-based instruction for recursion-based problem solving, where schemas come from Enumerative Combinatorics. This is the core of our attempt at developing second-year computer Engineering students' problem-solving skills. We provide the students with these schemas as templates in the C language to guide them step-by-step in solving search and optimization problems with uninformed and complete algorithms. To extend the applicability of this approach to other than small-size problems, we show students how they can introduce pruning to limit search while keeping it complete. We present experimental evidence we gathered for our second-year CS2+CS3 programming course for Computer Engineering students at Politecnico di Torino, a major technical university in Italy. We evaluate students' perception of the approach in terms of understanding and of ability to apply it. We compare students' perception to faculty expectations and we evaluate students' performance in terms of improvement in the success rate at exams. Data prove that the approach we adopt is beneficial both in terms of quantitative results (success rate at exams) and qualitative results (knowledge and skills acquired by students).