PDF Archive

Easily share your PDF documents with your contacts, on the Web and Social Networks.

Share a file Manage my documents Convert Recover PDF Search Help Contact



Grokking Algorithms .pdf


Original filename: Grokking Algorithms.pdf
Title: Grokking Algorithms
Author: Aditya Y. Bhargava

This PDF 1.7 document has been generated by Adobe InDesign CC 2014 (Macintosh) / Adobe PDF Library 11.0; modified using iText 2.1.7 by 1T3XT, and has been sent on pdf-archive.com on 27/11/2017 at 11:18, from IP address 78.140.x.x. The current document download page has been viewed 11692 times.
File size: 24.8 MB (258 pages).
Privacy: public file




Download original PDF file









Document preview


grokking

algorithms

grokking

algorithms
An illustrated guide for
programmers and other curious people

Aditya Y. Bhargava

MANNING
S helter I Sl and

For online information and ordering of this and other Manning books, please visit
www.manning.com. The publisher offers discounts on this book when ordered in
quantity. For more information, please contact
Special Sales Department
Manning Publications Co.
20 Baldwin Road, PO Box 761
Shelter Island, NY 11964
Email: orders@manning.com
©2016 by Manning Publications Co. All rights reserved.
No part of this publication may be reproduced, stored in a retrieval system, or
transmitted, in any form or by means electronic, mechanical, photocopying, or
otherwise, without prior written permission of the publisher.
Many of the designations used by manufacturers and sellers to distinguish their
products are claimed as trademarks. Where those designations appear in the book,
and Manning Publications was aware of a trademark claim, the designations have
been printed in initial caps or all caps.


Recognizing the importance of preserving what has been written, it is Manning’s
policy to have the books we publish printed on acid-free paper, and we exert our best
efforts to that end. Recognizing also our responsibility to conserve the resources of
our planet, Manning books are printed on paper that is at least 15 percent recycled
and processed without the use of elemental chlorine.
Manning Publications Co.
20 Baldwin Road
Shelter Island, NY 11964

Development editor: Jennifer Stout
Technical development editor: Damien White
Project manager: Tiffany Taylor
Copyeditor: Tiffany Taylor
Technical proofreader: Jean-François Morin
Typesetter: Leslie Haimes
Cover and interior design: Leslie Haimes
Illustrations by the author

ISBN: 9781617292231
Printed in the United States of America
1 2 3 4 5 6 7 8 9 10 – EBM – 21 20 19 18 17 16

For my parents, Sangeeta and Yogesh

vii

contents
preface

xiii

acknowledgments

xiv

about this book

xv

1 Introduction to algorithms
Introduction

1

Recap

1
2
2
3
5
10
10
11
13
15
15
17
19

2 Selection sort

21

What you’ll learn about performance
What you’ll learn about solving problems

Binary search
A better way to search
Running time

Big O notation
Algorithm running times grow at different rates
Visualizing different Big O run times
Big O establishes a worst-case run time
Some common Big O run times
The traveling salesperson

How memory works
Arrays and linked lists
Linked lists
Arrays
Terminology
Inserting into the middle of a list
Deletions

22
24
25
26
27
29
30

contents

viii

Selection sort
Recap

3 Recursion
Recursion
Base case and recursive case
The stack
The call stack
The call stack with recursion

Recap

4 Quicksort
Divide & conquer
Quicksort
Big O notation revisited
Merge sort vs. quicksort
Average case vs. worst case

Recap

5 Hash tables
Hash functions
Use cases
Using hash tables for lookups
Preventing duplicate entries
Using hash tables as a cache
Recap

Collisions
Performance
Load factor
A good hash function

Recap

6 Breadth-first search
Introduction to graphs
What is a graph?
Breadth-first search
Finding the shortest path

32
36
37
38
40
42
43
45
50
51
52
60
66
67
68
72
73
76
79
79
81
83
86
86
88
90
92
93
95
96
98
99
102


Related documents


chap4 b
designaadanalysissofalgorithmssyllabus
grokking algorithms
designaadanalysissofalgorithmsunit5
multireot
designaadanalysissofalgorithmsunit2


Related keywords