Daniel Zingaro - Algorithmic Thinking: A Problem-Based Introduction

A Problem-Based Introduction

by Daniel Zingaro

San Francisco

ALGORITHMIC THINKING. Copyright 2021 by Daniel Zingaro.

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.

ISBN-13: 978-1-7185-0080-8 (print)
ISBN-13: 978-1-7185-0081-5 (ebook)

Publisher: Bill Pollock
Executive Editor: Barbara Yien
Production Editor: Kassie Andreadis
Developmental Editor: Alex Freed
Interior Design: Octopod Studios
Cover Illustration: Rob Gale
Technical Reviewer: Larry Yueli Zhang
Copyeditor: David Couzens
Proofreader: James Fraleigh

For information on book distributors or translations, please contact No Starch Press, Inc. directly:
No Starch Press, Inc.
245 8th Street, San Francisco, CA 94103
phone: 1-415-863-9900;
www.nostarch.com

Library of Congress Cataloging-in-Publication Data

Names: Zingaro, Daniel, author.
Title: Algorithmic thinking : a problem-based introduction / by Daniel
Zingaro.
Description: San Francisco : No Starch Press, [2021] | Includes
bibliographical references and index.
Identifiers: LCCN 2020031510 (print) | LCCN 2020031511 (ebook) ISBN
9781718500808 (paperback) | ISBN 1718500807 (paperback) ISBN
9781718500815 (ebook)
Subjects: LCSH: Computer algorithms-Problems, exercises, etc. | Computer
programming-Problems, exercises, etc.
Classification: LCC QA76.9.A43 Z56 2020 (print) | LCC QA76.9.A43 (ebook)
| DDC 005.13-dc23
LC record available at https://lccn.loc.gov/2020031510
LC ebook record available at https://lccn.loc.gov/2020031511

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.

To Doyali

Dr. Daniel Zingaro is an assistant teaching professor of computer science and award-winning teacher at the University of Toronto. His main area of research is computer science education research, where he studies how students learn (and sometimes dont learn) computer science material.

Larry Yueli Zhang is an Assistant Professor, Teaching Stream of Computer Science at the University of Toronto Mississauga. His teaching and research interests include algorithms, data structures, operating systems, computer networks, social networks, and computing education. He has been in the program committees of ACM SIGCSE, ACM ITiCSE, and WCCCE. He holds a PhD in Computer Science from the University of Toronto.

HASH TABLES

TREES AND RECURSION

MEMOIZATION AND DYNAMIC PROGRAMMING

GRAPHS AND BREADTH-FIRST SEARCH

SHORTEST PATHS IN WEIGHTED GRAPHS

BINARY SEARCH

HEAPS AND SEGMENT TREES

UNION-FIND

A
ALGORITHM RUNTIME

B
BECAUSE I CANT RESIST

C
PROBLEM CREDITS

For the novice tennis player, keeping the ball in the court is hard enough (especially from the backhand side). Only after months of practice, once the basic rallying skills have been mastered, does the sport and its addictive nature begin to reveal itself. You add to your repertoire more advanced toolsa slice backhand, a kick serve, a drop volley. You strategize at a higher level of abstractionserve and volley, chip and charge, hug the baseline. You develop intuition for which tools and strategies will be most effective against different types of opponentstheres no silver-bullet approach that works well against everyone.

Programming is like tennis. For the beginning coder, coaxing the computer to understand what you want it to doto execute your solution to a problemis hard enough. Graduate from this white-belt level, and the true problem-solving fun begins: How do you come up with the solution in the first place? While theres no silver-bullet approach that solves every computational problem efficiently, there are enduringly useful advanced tools and strategies: hash tables, search trees, recursion, memoization, dynamic programming, graph search, and more. And to the trained eye, many problems and algorithms offer dead giveaways as to which tools are the right ones. Does your algorithm perform repeated lookups or minimum computations? Speed it up with a hash table or min-heap, respectively! Can you build a solution to your problem from solutions to smaller subproblems? Use recursion! Do the subproblems overlap? Speed up your algorithm with memoization!

Be it tennis or programming, you cant up your game to the next level without two things: practice and a good coach. To this end, I give you AlgorithmicThinking: A Problem-Based Introduction and Daniel Zingaro. This book teaches all the concepts that Ive mentioned, but it is no mere laundry list. With Zingaro as a tutor by your side, youll learn, through practice on challenging competition problems, a repeatable process for figuring out and deftly applying the right algorithmic tools for the job. And youll learn it all from a book that exudes clarity, humor, and just the right dose of Canadian pride. Happy problem-solving!

Tim Roughgarden

New York, NY

May 2020

What an idyllic experience it was to work with the folks at No Starch Press. Theyre all laser-focused on writing books to help readers learn. Ive found my people! Liz Chadwick supported my book from the start (and unsupported another oneIm grateful for that!). It is a gift to have worked with Alex Freed, my developmental editor. Shes patient, kind, and always eager to help me improve how I write instead of just fixing my mistakes. I thank all those involved in the production of the book, including my copyeditor David Couzens, production editor Kassie Andreadis, creative director Derek Yee, and cover designer Rob Gale.

I thank the University of Toronto for offering me the time and space to write. I thank Larry Zhang, my technical reviewer, for his careful review of the manuscript. Ive taught several courses with Larry over the years, and our collaboration has helped shape the way that I think about and teach algorithms.

I thank Tim Roughgarden for authoring the books foreword. Tims books and videos are examples of the kind of clarity that we need to strive for when teaching algorithms.