Algorithmic Thinking A Problem-Based Introduction (Early Access) (Daniel Zingaro)（Z-Library）

# Algorithmic Thinking: A Problem-Based Introduction ## 【One-Line Pitch】 A hands-on, competition-inspired guide that teaches you to design algorithms and choose data structures by solving real programming problems from USACO, IOI, and Codeforces — perfect for self-taught programmers who want to think like a problem solver, not just a coder. ## 【Book Arc】 - **Opening (~0%–9%)**: Sets up the book's philosophy — learn by solving problems from programming competitions, with code written in C from scratch (no reliance on built-in data structures). Introduces the workflow: read input, solve, submit to an online judge for free correctness checking. - **Early (~9%–25%)**: Dives into hash tables through the "Unique Snowflakes" problem, teaching collision handling, memory–time tradeoffs, and hash function design. Extends to compound word detection and spelling checks, showing when hashing beats brute force and when it doesn't. - **Early (~25%–34%)**: Shifts to trees and recursion, building binary tree structures from scratch with C structs. Covers recursive thinking — base cases, recursive cases — and introduces stacks as a tool for tree traversal. - **Middle (~34%–47%)**: Deepens recursion practice with tree problems like counting nodes and leaves, parsing tree strings with helper functions and pointer parameters, and sorting tree nodes with qsort using custom comparison functions. - **Middle (~47%–end of excerpts)**: Transitions into optimization problems, exemplified by the "Homer Simpson" burger problem — determining the maximum number of burgers eaten within a time limit, introducing the idea of characterizing optimal solutions before coding. ## 【Key Takeaways】 - **Hash tables solve "repeated slow search" problems** (Early): When brute-force comparison is too slow (e.g., checking 100,000 snowflakes for twins), hashing groups similar items into buckets, turning O(n²) into near-linear time. The hash function must guarantee identical items land in the same bucket. - **Memory–time tradeoff is a core design decision** (Early): A small hash table causes collisions and long linked lists; a large one wastes memory. Choosing the right size and hash function is a balancing act you must consciously make. - **Recursion requires a base case and a recursive case** (Early): For trees, the base case is a leaf (return 1); the recursive case combines results from left and right subtrees. This pattern — solve the easy case directly, decompose the hard case — applies to counting nodes, leaves, and more. - **Helper functions with pointer parameters manage recursion state** (Middle): When a recursive function needs to track position (e.g., parsing a tree string), add a helper with an extra pointer parameter. The public function stays clean; the helper carries the internal state. - **Custom comparison functions unlock sorting** (Middle): With qsort, you write a comparator that returns negative, zero, or positive. For trees, compare scores first, then break ties alphabetically with strcmp — a reusable pattern for any custom sort. - **Optimization problems need characterization before coding** (Middle): For the burger problem, the plan is to test whether exact time t is achievable, then t−1, t−2, and so on — decrementing until a solution fits. Think about the structure of optimal solutions before writing loops. ## 【Reading Tips】 - **Skim the early code listings** (Chunk 3–4): The "shortest line" and "identical integers" examples are warm-ups. Read them for the pattern (helper function + main loop), not the details — the real payoff is in the hash table and tree chapters. - **Deep-read the hash table chapter** (Chunk 6–7): The snowflake problem is the book's anchor. Pay close attention to why the hash function must respect what "identical" means — this insight transfers to every hashing problem. - **Expect recursion to feel hard** (Chunk 12–13): The tree_nodes and tree_leaves functions look deceptively simple. Trace them by hand with a small tree before moving on. The helper-function-with-pointer trick in read_tree is subtle — reread it twice. - **Practice with the online judges**: Every problem has a URL and ID. Don't just read — submit your code. The judge's verdict is the ultimate feedback loop. - **Skip the C-specific details if you're not a C programmer**: The book's lessons on algorithm design and data structure choice are language-agnostic. Focus on the "why" behind each choice, not the malloc syntax. ## 【Coverage Limits】 The excerpts cover the introduction, hash tables, and the start of trees/recursion, plus a glimpse of optimization problems. They do not cover later chapters on breadth-first search, Dijkstra's algorithm, union-find, heaps, dynamic programming, or binary search — all promised in the book's blurb but absent from this sample. ##