The Imposter’s Handbook: A CS Primer for Self-Taught Developers

Cover Photo Credit......Page 1
Preface......Page 4
A Few Notes, Before We Begin......Page 5
How I Wrote This......Page 7
The Law of Large Bunnies......Page 9
Finally: A Thank You......Page 10
Foreword: Scott Hanselman......Page 12
Foreword: Chad Fowler......Page 14
Complexity Theory......Page 20
The Bunny Optimization Problem (BOP)......Page 21
Quantifying "How Hard"......Page 23
Simple Problems And Polynomial Time (P)......Page 24
Hard Problems......Page 27
Exp......Page 28
Nondeterminism and NP......Page 33
Decision Problems......Page 35
Complexity Classifications......Page 37
NP-Hard......Page 38
NP-Complete......Page 40
Does P=NP?......Page 44
A Quick Game To Clear Our Heads......Page 45
R......Page 47
Impossibly Hard: Not Being Able To Decide......Page 50
Big-O......Page 54
O(1)......Page 55
O(n)......Page 57
Order n^2......Page 59
O(log n) and O(n log n)......Page 66
Lambda Calculus......Page 72
The Basics of Lambda Calculus......Page 74
Identity and Constant Functions......Page 76
Bound and Free Variables......Page 77
Function Application And Beta Reduction......Page 79
Church Encoding......Page 81
Conditional Expressions......Page 83
Combinators......Page 84
The Y Combinator......Page 85
Summary......Page 86
Computation......Page 88
Is Reality Just a Computer Program?......Page 92
Nature’s Strange programs......Page 94
What Is Computation?......Page 99
The Difference Engine......Page 101
Turing’s Machine......Page 110
The Halting Problem......Page 118
The Von Nuemann Machine......Page 122
Other Machinery You Should Know......Page 132
Data Structures......Page 148
Arrays......Page 150
Linked Lists......Page 153
Hash Table......Page 157
Heap......Page 162
Binary Search Tree......Page 165
Graphs......Page 170
Graph Theory......Page 171
The Bridges of KÖnigsberg......Page 172
So What?......Page 176
Directed And Undirected Graphs......Page 177
Weighted and Unweighted Graphs......Page 178
Directed Acyclic Graphs (DAGs)......Page 181
Algorithms......Page 183
The Code......Page 184
Bubble Sort......Page 185
Merge Sort......Page 191
Quicksort......Page 197
Selection Sort......Page 205
Heap Sort......Page 211
Binary Search......Page 222
Definition......Page 229
Origins......Page 230
Definition......Page 232
Calculating Fibonacci The Slow Way......Page 233
Calculating Fibonacci The faster way: using Memoization......Page 239
The Sieve of Eratosthenes......Page 242
Break It Down......Page 248
Once Again, With More Recursion......Page 250
Was This Dynamic Programming?......Page 252
The Problem Graph......Page 254
Setting Up......Page 256
Iteration 1......Page 258
Iteration 2......Page 261
Iteration 3......Page 264
Again, With JavaScript......Page 265
Analysis and Summary......Page 268
The Setup......Page 270
Starting At The Source......Page 271
Traversing Each Vertex......Page 272
Implementing Dijkstra With JavaScript......Page 277
Programming Languages......Page 283
How a Compiler Works......Page 286
Lexical Analysis......Page 287
Parsing......Page 288
Semantic Analysis......Page 289
Lexical Scoping......Page 291
Optimization......Page 293
Code Gen......Page 295
LLVM......Page 297
GCC......Page 298
Microsoft .NET CLR......Page 300
Java JVM......Page 301
Ruby's Various Interpreters......Page 302
Python......Page 303
A Quick Overview......Page 306
The Stack......Page 308
The Heap......Page 310
Garbage Collection......Page 313
Tracing......Page 314
Reference Counting......Page 317
Compile-time......Page 320
Just Start......Page 322
Step 1: The Editor......Page 323
Step 2: Docs......Page 324
Step 3: Start Small By Creating a Project......Page 327
Step 4: Write a Test......Page 328
Step 5: Investigate Basic Types......Page 334
Step 6: Investigating Lists and Enumerations......Page 335
Step 7: Idioms......Page 338
Step 8: Refactor Something For Fun......Page 344
Step 9: Building Something......Page 347
Step 10: Get Involved......Page 348
Databases......Page 350
Normalization......Page 352
OLAP and OLTP......Page 367
Distributed Database Systems......Page 381
Big Data......Page 396
Software Design......Page 409
The Code......Page 413
Constructor......Page 414
Factory......Page 415
Builder......Page 420
Method Chaining......Page 421
Singleton......Page 422
Adapter......Page 424
Bridge......Page 425
Composite......Page 426
Decorator......Page 429
Facade......Page 430
Flyweight......Page 432
Chain of Responsibility......Page 433
Command......Page 437
Mediator......Page 439
Observer......Page 440
State......Page 442
Strategy......Page 443
Functional Programming......Page 447
Immutability......Page 448
Purity......Page 450
Side Effects......Page 451
Currying......Page 452
Coupling and Cohesion......Page 457
Separation of Concerns......Page 458
YAGNI and DRY......Page 461
Tell, Don't Ask......Page 462
Law Of Demeter (or: Principle of Least Knowledge)......Page 463
Dependency Injection......Page 467
Interface-based Programming......Page 469
Inversion of Control......Page 472
Single Responsibility......Page 477
Open/Closed......Page 479
Liskov Substitution......Page 480
Interface Segregation......Page 482
Dependency Inversion......Page 484
Dependency Inversion vs. Dependency Injection......Page 487
Some Opinion About Testing In General......Page 488
As Close To a Real Example As I Can Get......Page 489
Just Start......Page 490
The Customer......Page 491
The Happy Path......Page 495
The Sad Path......Page 501
In The Real World......Page 509
Getting Started With BDD......Page 510
Should......Page 517
Feature, Context, Spec, and Scenario......Page 519
Missing The Mark, Just a Little......Page 521
In The Real World......Page 523
Summary......Page 525
Essential Unix Tools......Page 526
The Code......Page 527
What Is a Shell?......Page 529
Why Script a Shell?......Page 533
One Last Thing......Page 534
A Simple First Step......Page 536
STDOUT and STDIN......Page 539
Creating An Executable Script......Page 540
Command and Parameter Expansion......Page 548
For Loops......Page 549
If Statements......Page 551
Quoting......Page 553
Using ImageMagick......Page 554
Using Functions......Page 555
Execution vs. Loading......Page 558
Start With a Function......Page 562
Creating a Slug......Page 563
The sed Command......Page 565
There’s Always a Better Way......Page 567
Adding Front matter With a Heredoc......Page 568
The Basics......Page 572
Anatomy of a Makefile......Page 573
Understanding Targets......Page 574
The Simplest Operation......Page 575
Orchestrating The Build......Page 578
Using Variables......Page 580
Using Make To Build Your Web Project......Page 587
The Web Project......Page 588
Step 2: Our Makefile Skeleton......Page 589
Step 3: Define The Variables......Page 590
Step 4: Define The Targets......Page 592
Step 5: Building The Files......Page 594
Ordering Of Files......Page 596
Summary......Page 597
The Basics......Page 598
A Real World Scenario......Page 600
Execution As Another User......Page 602
Going Further......Page 603
Wrapping Up......Page 604
One Final Thought......Page 607