Sorting algorithms are frequently taught in data structures courses to expose students to algorithmic thinking and asymptotic complexity. In this lecture, we will introduce the selection sort algorithm. As we implement selection sort, we will use program annotations (contracts) to define and reason about the correctness of our code. Time permitting, we will formally prove the correctness of our selection sort implementation. We will also review big-O notation to determine its running time.

Hannah (Anna) Gommerstadt is a PhD candidate in the Computer Science Department at Carnegie Mellon University where she works with Frank Pfenning and Limin Jia. Her research interests are at the intersection of programming languages and security especially the use of language-based and logic-based methods to provide formal security guarantees. Her current work focuses on dynamic monitoring and contract enforcement in a concurrent setting. She obtained her B.A. in Computer Science and Mathematics from Harvard University.