We will (start to) discuss big-O, at the level of CS 173. We will discuss the definition of big-O, in particular why the definition we use is the "right" one. Then we'll practice one of the common techniques for writing those proofs. I will assume the audience understands nested quantifiers and have a notion of what a proof is (i.e., have taken the first few weeks into CS 173).
Robbie Weber is a Ph.D. candidate at the University of Washington. His research is broadly in the design and analysis of algorithms, particularly on graph problems, and in answering combinatorial questions. He is advised by Anna Karlin and Shayan Oveis Gharan. At the University of Washington, he has been the instructor of record for two data structures courses, and has been a TA for eight different courses (ranging from discrete math, to machine learning, to graduate algorithms). He received his undergraduate degree from the University of Illinois at Urbana-Champaign, where he was an undergraduate TA for seven semesters (most of them working for CS 173). In teaching, he works to make theoretical computer science accessible to large numbers of students and to give students more chances to participate in lectures.
Faculty Host: Eric Shaffer