For information regarding permissions, request forms, and the appropriate contacts within the Pearson Education Global Rights & Permissions Department, please visit ISBN-13: ISBN-10: Text printed in the United States on recycled paper at RR Donnelley in Crawfordsville, Indiana. This publication is protected by copyright, and permission must be obtained from the publisher prior to any prohibited reproduction, storage in a retrieval system, or transmission in any form or by any means, electronic, mechanical, photocopying, recording, or likewise. For information about buying this title in bulk quantities, or for special sales opportunities (which may include electronic versions custom cover designs and content particular to your business, training goals, marketing focus, or branding interests), please contact our corporate sales department at or (800) For government sales inquiries, please contact For questions about sales outside the United States, please contact Visit us on the Web: /aw Library of Congress Control Number: Copyright 2017 Pearson Education, Inc. No liability is assumed for incidental or consequential damages in connection with or arising out of the use of the information or programs contained herein. The authors and publisher have taken care in the preparation of this book, but make no expressed or implied warranty of any kind and assume no responsibility for errors or omissions. Where those designations appear in this book, and the publisher was aware of a trademark claim, the designations have been printed with initial capital letters or in all capitals. 4 Computer Science An Interdisciplinary Approach Robert Sedgewick Kevin Wayne Princeton University Boston Columbus Indianapolis New York San Francisco Amsterdam Cape Town Dubai London Madrid Milan Munich Paris Montreal Toronto Delhi Mexico City Sāo Paulo Sydney Hong Kong Seoul Singapore Taipei Tokyoĥ Many of the designations used by manufacturers and sellers to distinguish their products are claimed as trademarks.