Programming for the Puzzled

by Devadas

ISBN: 9780262343183 | Copyright 2017

Click here to preview

Instructor Requests

Digital Exam/Desk Copy Print Exam/Desk Copy Ancillaries
Tabs

This book builds a bridge between the recreational world of algorithmic puzzles (puzzles that can be solved by algorithms) and the pragmatic world of computer programming, teaching readers to program while solving puzzles. Few introductory students want to program for programming's sake. Puzzles are real-world applications that are attention grabbing, intriguing, and easy to describe.

Each lesson starts with the description of a puzzle. After a failed attempt or two at solving the puzzle, the reader arrives at an Aha! moment -- a search strategy, data structure, or mathematical fact -- and the solution presents itself. The solution to the puzzle becomes the specification of the code to be written. Readers will thus know what the code is supposed to do before seeing the code itself. This represents a pedagogical philosophy that decouples understanding the functionality of the code from understanding programming language syntax and semantics. Python syntax and semantics required to understand the code are explained as needed for each puzzle.

Readers need only the rudimentary grasp of programming concepts that can be obtained from introductory or AP computer science classes in high school. The book includes more than twenty puzzles and more than seventy programming exercises that vary in difficulty. Many of the puzzles are well known and have appeared in publications and on websites in many variations. They range from scheduling selfie time with celebrities to solving Sudoku problems in seconds to verifying the six degrees of separation hypothesis. The code for selected puzzle solutions is downloadable from the book's website; the code for all puzzle solutions is available to instructors.

Expand/Collapse All
Contents (pg. v)
Preface (pg. vii)
Acknowledgments (pg. xi)
1. You Will All Conform (pg. 1)
Finding Sequences of Like-Minded People (pg. 2)
Strings, Lists, and Tuples (pg. 4)
From Algorithm to Code (pg. 4)
Code Optimization (pg. 7)
List Creation and Modification (pg. 7)
Scoping (pg. 8)
An Algorithmic Optimization (pg. 9)
A One-Pass Algorithm (pg. 9)
Applications (pg. 10)
Exercises (pg. 11)
2. The Best Time to Party (pg. 13)
Checking Time and Time Again (pg. 14)
Being Smart About Checking Times (pg. 16)
Sorted Representation (pg. 20)
Exercises (pg. 20)
3. You Can Read Minds (with a Little Calibration) (pg. 23)
Coding the Assistant’s Job (pg. 25)
Coding the Magician’s Job (pg. 29)
Mastering the Trick in Solitude (pg. 31)
Encoding Information (pg. 33)
Magic Trick with Four Cards (pg. 34)
Exercises (pg. 35)
4. Keep Those Queens Apart (pg. 37)
Systematic Search (pg. 40)
Board as a 2-D List/Array (pg. 41)
Board as a 1-D List/Array (pg. 44)
Iterative Enumeration (pg. 49)
Exercises (pg. 50)
5. Please Do Break the Crystal (pg. 51)
Efficient Search with Two Balls (pg. 52)
Efficient Search with d Balls (pg. 53)
Reducing the Number of Drops for Two Balls (pg. 57)
Exercises (pg. 58)
6. Find That Fake (pg. 59)
Divide and Conquer (pg. 60)
Recursive Divide and Conquer (pg. 61)
Ternary Representation (pg. 65)
A Popular Variant Weighing Puzzle (pg. 65)
Exercises (pg. 65)
7. Hip to Be a Square Root (pg. 67)
Iterative Search (pg. 67)
Bisection Search (pg. 71)
Binary Search (pg. 72)
Ternary Search? (pg. 74)
Exercises (pg. 75)
8. Guess Who Isn’t Coming to Dinner (pg. 77)
First Attempt (pg. 78)
Always Finding the Maximum Selection (pg. 79)
Generating All Combinations (pg. 81)
Removing Unfriendly Combinations (pg. 82)
Choosing the Minimum Combination (pg. 83)
Optimizing Memory Usage (pg. 84)
Applications (pg. 85)
Exercises (pg. 85)
9. America’s Got Talent (pg. 89)
Generating and Testing One Combination at a Time (pg. 91)
Determining Combinations That Lack a Talent (pg. 92)
Applications (pg. 93)
Exercises (pg. 94)
10. A Profusion of Queens (pg. 97)
Recursive Greatest Common Divisor (pg. 98)
Recursive Fibonacci (pg. 99)
Recursive N-queens (pg. 101)
Applications of Recursion (pg. 103)
Exercises (pg. 106)
11. Tile That Courtyard, Please (pg. 109)
Merge Sort (pg. 110)
Merge Sort Execution and Analysis (pg. 112)
Base Case of a 2 × 2 Courtyard (pg. 114)
Recursive Step (pg. 114)
List Comprehension Basics (pg. 118)
Pretty Printing (pg. 119)
A Different Tiling Puzzle (pg. 121)
Exercises (pg. 121)
12. The Towers of Brahma with a Twist (pg. 123)
Recursive Solution of TOH (pg. 124)
Recursive Solution of ATOH (pg. 126)
Relationship to Gray Codes (pg. 130)
Exercises (pg. 131)
13. The Disorganized Handyman (pg. 135)
Pivoting in Divide-and-Conquer (pg. 136)
Relationship to Sorting (pg. 137)
In-Place Partitioning (pg. 140)
Sort Mania (pg. 143)
Exercises (pg. 143)
14. You Won’t Want to Play Sudoku Again (pg. 147)
Recursive Sudoku Solving (pg. 148)
Implications during Recursive Search (pg. 153)
Difficulty of Sudoku Puzzles (pg. 157)
Exercises (pg. 158)
15. Counting the Ways You Can Count Change (pg. 161)
Recursive Bill Selection (pg. 162)
Eliminating Repetition (pg. 163)
Making Change with the Fewest Bills (pg. 165)
Exercises (pg. 166)
16. Greed Is Good (pg. 169)
A Greedy Approach (pg. 170)
Shortest Duration Rule (pg. 170)
Earliest Start Time Rule (pg. 171)
Fewest Conflicts Rule (pg. 171)
Earliest Finish Time Rule (pg. 172)
When Is Greed Good? (pg. 176)
Exercises (pg. 177)
17. Anagramania (pg. 181)
Finding Anagram Groupings One at a Time (pg. 182)
Anagram Grouping via Sorting (pg. 183)
Anagram Grouping via Hashing (pg. 185)
Dictionaries (pg. 186)
Using Dictionaries to Group Anagrams (pg. 188)
Hash Tables (pg. 190)
Exercises (pg. 191)
18. Memory Serves You Well (pg. 193)
Recursive Solution (pg. 194)
Tracing Back Coin Selection (pg. 196)
Memoization (pg. 198)
Avoiding Exceptions (pg. 200)
Dynamic Programming (pg. 200)
Exercises (pg. 201)
19. A Weekend to Remember (pg. 205)
Finding a Partition (pg. 207)
Checking If a Graph Is Bipartite (pg. 209)
Graph Representation (pg. 211)
Graph Coloring (pg. 214)
Exercises (pg. 215)
20. Six Degrees of Separation (pg. 219)
Breadth-First Search (pg. 221)
Sets (pg. 223)
Using Sets in Breadth-First Search (pg. 224)
History (pg. 227)
Exercises (pg. 228)
21. Questions Have a Price (pg. 231)
Binary Search Trees Using Dictionaries (pg. 234)
Operations on BSTs under a Dictionary Representation (pg. 235)
OOP-Style Binary Search Trees (pg. 239)
Back to Our Puzzle: Algorithm (pg. 243)
Code to Solve Our Puzzle (pg. 245)
Comparing Data Structures (pg. 249)
Exercises (pg. 249)
Notes (pg. 251)
Preface (pg. 251)
Chapter 1 (pg. 251)
Chapter 2 (pg. 251)
Chapter 3 (pg. 251)
Chapter 4 (pg. 251)
Chapter 5 (pg. 251)
Chapter 8 (pg. 251)
Chapter 9 (pg. 252)
Chapter 11 (pg. 252)
Chapter 13 (pg. 252)
Chapter 14 (pg. 252)
Chapter 15 (pg. 252)
Chapter 16 (pg. 252)
Chapter 17 (pg. 252)
Chapter 18 (pg. 252)
Chapter 21 (pg. 253)
Index (pg. 255)
eTextbook
Go paperless today! Available online anytime, nothing to download or install.

Features

  • Bookmarking
  • Note taking
  • Highlighting
Support