Making Theoretical Computer Science Approachable to High School Students

Theoretical computer science is a branch of computer science that studies the fundamentals of modern computing systems and establishes what computers can and cannot achieve.  Although AI and games theory engage the public, theoretical computer science tends to be overlooked because of its complexity, but it nonetheless plays a key role in large datasets such as scheduling airline flights or school schedules, etc. Professor Mukund Raghothaman, an Assistant Professor in the University of Southern California's Computer Science Department, introduced the concept of constraint satisfaction problems (CSPs) to our 2021 SHINE program on June 23^rd, and opened the door to the theoretical realm of computer science. 

CSPs are questions for which solutions are required to fulfill specified constraints and limits. Solving constraint satisfaction problems has piqued the interest of computer scientists for decades, as it will assist in making better decisions. Computer scientists can solve individual puzzles like Crosswords or the Eight Queen Puzzle as well as complex large-scale difficulties like airport scheduling and internet routing by identifying the problems and discovering solutions using constraint-based modeling. 

Professor Raghothaman began his presentation by posing a seating arrangement problem that could be solved by hand calculations. The SHINE students then worked in small groups to assist the main character, Alice, with seating arrangements for her high farewell party. There are also some conditions that add the complexity of the question, such as one of her friends refusing to sit next to another. Many groups were able to come up with multiple solutions to the challenge and assisted Alice in arranging the seats.  

Professor Raghothaman then taught the students how to translate the word problem into a graph representation that can be converted into computer commands. He briefly explained graph theory and demonstrated how computer scientists break down a basic real-world problem into vertices and edges in a graph. The students also learned how a simple seat arrangement problem may be expanded and scaled up to a complex real-world scenario, requiring computer scientists to build algorithms to find the solutions utilizing machines. 

While not everyone is cut out to be a computer scientist, computational thinking helps anyone to build 21st-century skills. By researching CSPs with Professor Raghothaman, the SHINE students enhanced their abilities to understand complicated situations through the lens of constraints and filter key details from wordy descriptions. Decomposition and abstraction skills are both important components of developing computational thinking skills, which allows our SHINE students to be more creative with computational tools. 

Beyond SHINE, the K12 STEM Center will continue to seek to provide K-12 students and teachers with top-tier, high-quality computer science instruction and support.