Algorithmic Thinking: A Problem-Based Introduction
Hi DMOJ!
Dr. Daniel Zingaro "" of the University of Toronto has recently been working on a book introducing contest programming concepts in a practical way. It's nearing completion, so we thought we'd let you know! I'll let Dr. Zingaro handle the introduction:
Programming is about using a computer to solve problems, and algorithms and data structures are the building blocks of computer programs. For each problem that a programmer wants to solve, they employ an algorithm: a sequence of steps for solving the problem. Many books teach algorithms independently of specific problems, but this book uses careful explanations, examples, and arguments, rather than formal mathematics and proofs which make it difficult for you to connect what you are learning to what you can do with that learning. Algorithmic Thinking: A Problem-Based Introduction teaches you to use the best algorithms and data structures for a given situation by walking you through solving problems pulled from international programming competitions, such as how to determine whether snowflakes are unique; how to win a game in the minimum number of moves; how to find the number of ways to get to someone's house; how to escape a cave in as few steps as possible; and so on.
You'll tackle challenging topics like recursion, dynamic programming, graphs, greedy algorithms, heaps, hash tables, segment trees, and other data structures for efficiently handling data. The book contains no pseudocode: all code is written in C and is thoroughly explained in the text (C is a de facto programming language for programming competitions). By the end of the book, you should understand the importance of carefully working through a problem, and why it pays to organize data using data structures.
Algorithmic Thinking: A Problem-Based Introduction will be out in print in October, but it's available as an Early Access ebook now. Chapters will become available as soon as they're copyedited; the first four chapters are available now (including a free first chapter), and the rest will follow in a few weeks.
The book uses problems from various online judges (including DMOJ!) as exercises, which sounds like a fun, hands-on way to pick up new tricks.
We're also excited to give away some copies in future DMOJ competitions, so watch out for that :)
Comments
Hi rpeng and all,
We have the first four chapters available in Early Access now, including the DP chapter (Chapter 3).
One of the things I wanted to do in the book was to go slowly, to provide as much detail as I could. Why can't we just use loops instead of recursion? Why can't we just use recursion instead of DP? Why can't we just use linear search instead of binary search? Why can't we use BFS instead of union-find? I spend a lot of time trying to give the reader intuition for why we do things, not just how.
I agree that DP is a whole course. Recursion may be a whole course, too. It can take a long time to master this stuff. Everyone has their own pace. I try to encourage readers through my book to ignore how "easy" other people may say it is, and to keep with it.
I'd love to write an entire book on Dynamic Programming. There are so many wonderful DP problems here on DMOJ. Is it just me or is DP way less 'formulaic' than is often let on? In particular, I still sometimes find it challenging to come up with the subproblem space.
I introduce trees very early so that we can use them to springboard into graphs (Chapter 4), and to show them as a component in binary-search algorithms (Chapter 6). My hope is that the reader will then be familiar enough with trees so that heaps and segment trees are more intuitive.
Thank you! Dan
The provided link only has download for chapter 1. Where can I take a look at the DP chapter (3)?
I've maintained for a long time that just DP alone is a full course, and the same also goes for trees/heaps/segtrees (which strangely is spread out in 2 & 7?). Starting with how to use arrays/sorting is long overdue though :-).