Jeremy Kubica - The CS Detective: An Algorithmic Tale of Crime, Conspiracy, and Computation

An Algorithmic Tale of Crime, Conspiracy, and Computation

jeremy kubica

SAN FRANCISCO

THE CS DETECTIVE. Copyright 2016 by Jeremy Kubica.

All rights reserved. No part of this work may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, recording, or by any information storage or retrieval system, without the prior written permission of the copyright owner and the publisher.

Printed in USA

First printing

20 19 18 17 16 1 2 3 4 5 6 7 8 9

ISBN-10: 1-59327-749-0

ISBN-13: 978-1-59327-749-9

Publisher: William Pollock

Production Editor: Riley Hoffman

Cover and Interior Design: Beth Middleworth

Illustrator: Miran Lipovaa

Developmental Editor: Liz Chadwick

Technical Reviewer: Heidi Newton

Copyeditor: Rachel Monaghan

Compositor: Riley Hoffman

Proofreader: Paula L. Fleming

For information on distribution, translations, or bulk sales, please contact No Starch Press, Inc. directly:

No Starch Press, Inc.

245 8th Street, San Francisco, CA 94103

phone: 415.863.9900;

www.nostarch.com

Library of Congress Cataloging-in-Publication Data

Names: Kubica, Jeremy.

Title: The CS detective : an algorithmic tale of crime, conspiracy, and computation / by Jeremy Kubica.

Description: San Francisco : No Starch Press, [2016] | Summary: A mystery novel for computer science students and enthusiasts that introduces the concepts behind search algorithms and data structures. Each chapter teaches a new concept, ending with a technical explanation.-- Provided by publisher.

Identifiers: LCCN 2016013632 (print) | LCCN 2016026435 (ebook) | ISBN 9781593277499 (pbk.) | ISBN 1593277490 (pbk.) | ISBN 9781593277871 (epub) | ISBN 1593277873 (epub) | ISBN 9781593277888 (mobi) | ISBN 1593277881 (mobi)

Subjects: | CYAC: Algorithms--Fiction. | Computer science--Fiction. | Mystery and detective stories.

Classification: LCC PZ7.1.K8 Cs 2016 (print) | LCC PZ7.1.K8 (ebook) | DDC [Fic]--dc23

LC record available at https://lccn.loc.gov/2016013632

No Starch Press and the No Starch Press logo are registered trademarks of No Starch Press, Inc. Other product and company names mentioned herein may be the trademarks of their respective owners. Rather than use a trademark symbol with every occurrence of a trademarked name, we are using the names only in an editorial fashion and to the benefit of the trademark owner, with no intention of infringement of the trademark.

The information in this book is distributed on an As Is basis, without warranty. While every precaution has been taken in the preparation of this work, neither the author nor No Starch Press, Inc. shall have any liability to any person or entity with respect to any loss or damage caused or alleged to be caused directly or indirectly by the information contained in it.

All characters in this publication are fictitious, and any resemblance to real persons, living or dead, is purely coincidental.

Jeremy Kubica is a principal engineer at Google working on machine learning and algorithms. He has a PhD in robotics from Carnegie Mellon University and a BS in computer science from Cornell University. He spent his graduate school years creating algorithms to detect killer asteroids (actually stopping them was, of course, left as future work). Kubica is the author of the popular Computational Fairy Tales blog.

Heidi Newton has a BSc from the University of Canterbury, New Zealand, and an MSc from Victoria University of Wellington, New Zealand, both in computer science. She works for the University of Canterburys computer science education research group and Code Avengers, and on the side carries out related tutoring and consultancy work. Her current focus is on improving teaching resources for computer science and programming.

I am tremendously grateful to all the people who contributed to, worked on, and supported this book.

I would like to start by thanking the whole team at No Starch Press. In particular, I would like to thank Liz Chadwick and Riley Hoffman for their excellent help, guidance, and suggestions during the editing process. Lizs brilliant suggestions were invaluable for keeping the story focused and moving. I am also grateful for her ideas in shaping the lecture notes format of the technical sections. Thank you to Bill Pollock and Tyler Ortman for their support, and a special thanks to Bill for suggesting the title. I would also like to thank Carlos Bueno for pointing me to No Starch Press.

Thank you to Miran Lipovaa for his amazing illustrations. They truly capture the characters and the story.

Thank you to Heidi Newton for her thorough and insightful technical review. Her work was vital in ensuring the concepts came across both accurately and understandably. I appreciate the number of times she warned of explanations being too technical and thus inaccessible to students.

A tremendous thanks goes out to all the people who slogged through earlier versions of this book and provided valuable feedback: John Bull, Mike Hochberg, Edith Kubica, Regan Lee, and Kristen Kit Stubbs, PhD. Thank you to Ilana Schwarcz, who edited the earlier version of the manuscript and helped smooth out many of the rough edges.

A deep thank you to my family for their support. In particular, thank you to my parents for supporting my interest in computer science as a kid and for providing significant encouragement for this book.

This book focuses on computational thinking and search algorithms. The stories introduce and illustrate computational concepts at a high level, exploring the motivation behind them and their application in a noncomputer domain. This book is not a comprehensive text, and the stories are not intended as a substitute for a solid technical description of computer science. Instead, they are meant to be used like illustrations: they supplement the full concept and aid understanding.

The book covers a variety of computational approaches that all share the broad categorization of search algorithms. Concepts are presented first within the context of the story, and then explained more technically in a section laid out as lecture notes at the end of each chapter. Readers can safely skip these technical sections without missing any of the story.

This book assumes some experience with basic computer science concepts but does not require knowledge of any specific programming language. The algorithms in this book are meant to apply to a range of programming languages and problem domains.

The door opened without a knockonly the hinges creak announced the visitor. Frank started for his crossbow, but pulled up short. If the Vinettees were coming for him, they would have knockedwith an axe. Whoever was coming through the door must want to talk. Frank reached for his mug instead and downed the remainder of his now-cold coffee.

Captain Donovan, he said as the man entered. What brings you to this fine neighborhood? I thought you didnt venture below Fifteenth Street anymore.

Its been a while, the captain said simply. Howve you been, Frank?

Spectacular, Frank answered dryly, eyeing the captain as he walked a slow circuit around the room.