Combining Theory and Practice in Data Structures & Algorithms Course Projects: An Experience Report

CS2 course projects can often be too prescriptive by telling students which algorithms or data structures are necessary to efficiently solve a given problem. Students may not fully understand why these algorithms or data structures were chosen, and they may not have an opportunity to empirically observe the impact of such design decisions. In 2019, we redesigned our CS2 course projects at North Carolina State University to help demonstrate the importance of critical-thinking and analysis activities when developing software. The objective of the redesigned course project is to connect computer science theory with software development practice by incorporating algorithm design and analysis, data structure selection, and experimental analysis as part of the software development lifecycle. For the project, students first create a design proposal that incorporates algorithm design and analysis, data structure selection, and other software design tasks. Next, students implement and test their software, while teaching staff test cases impose grade penalties for incorrect and/or inefficient implementations. Finally, students perform experimental analysis to empirically observe performance differences when using different data structures. Between January 2019 and May 2020, we collected end-of-course survey responses from 202 out of 536 students (37.7% response rate). Overall, 90.6% of respondents indicated that the project helped with understanding the importance of analysis and design when developing software. In this paper, we discuss our project activities in detail, along with lessons learned and suggestions for adopting similar projects in other CS2 courses.