Foundations of Data Science1 John Hopcroft Ravindran Kannan Version 11/4/2014 These notes are a first draft of a book being written by Hopcroft and Kannan and in many places are incomplete. However, the notes are in good enough shape to prepare lectures for a modern theoretical course in computer science. Please do not put solutions to exercises online as it is important for students to work out solutions for themselves rather than copy them from the internet. Thanks JEH 1Copyright 2011. All rights reserved 1 Contents 1 Introduction 7 2 High-Dimensional Space 10 2.1 Properties of High-Dimensional Space . . . . . . . . . . . . . . . . . . . . . 12 2.2 The Law of Large Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.3 The High-Dimensional Sphere . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.3.1 The Sphere and the Cube in High Dimensions . . . . . . . . . . . . 16 2.3.2 Volume and Surface Area of the Unit Sphere . . . . . . . . . . . . . 17 2
