Recommended Books

In the following, I want to share my recommended books during years 2014-2021 (i.e., from my master period to present).

Math

After reading the following books, I found I might never be an expert in math (especially after reading the “discrete mathematic”).

Ronald L. Graham, Donald E. Knuth, Oren Patashnik. “Concrete Mathematics: A Foundation for Computer Science, 2nd Ed.” Addison-Wesley, 1994.

This book (chinese version translated by Mingyao Zhang and Fan Zhang) was the only math book that I have read over. Although I also tried to do the exercises after each chapter, unfortunately, I only finished the exercises of half chapters.

Wanling Qu, Suyun Geng, Liang Zhang. “Discrete mathematic.” Peking University Press, 2002.

This is a chinese textbook which includes fundamental concepts and results in discrete mathematic. I have tried to read over this book for more than three times, but I failed at each time. I summarized some fundamental concepts in graph theory in this PDF (in chinese), which helps me a lot in my current Ph.D study.

Algorithm Design

During my research studies, I have learned a lot from the following books on data structure and algorithm design. For each book, I always try to read over all the chapters. For basic algorithm design, I think CLRS and ACM ICPC books are good enough to learn the elementary knowledge. I also pick only few chapters in TAOCP Vol.3. For advanced algorithm design, I first read two books on computation theory and then books on approximation/randomized algorithms. Now, I am still reading books related to algorithm design, but on more specific topics.

Preliminary

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. “Introduction to Algorithms, 3rd Edition.” MIT Press and McGraw-Hill, 2009.

It takes me over one year (2014~2015) to read over this book (chinese version translated by Jianping Yin et al.). I also do a lot of exercises and coding work after each chapter. Here are some of my answers for chapters 11-20 (in chinese).

Ruijia Liu et al. Colorful books on ACM ICPC (e.g., the blue/purple/black book).

I finished reading these books until year 2016. The algorithms (such as dynamic programming and range minimum queries), I learned from these books, turned out to be extremely important to my Ph.D study. To learn these algorithms, I keep doing exercises on Codeforces and HDU OJ during my whole master period. I used to be #17 in the top rank list of HDU OJ. Altough I haven’t submitted in HDU OJ for nearly four years, I have checked I am still #54 now (ID: Trasier). Independent thinking is the most important thing I have learned from the OJ exercises.

Computation Complexity

Michael Siper. “Introduction to the Theory of Computation, 3rd Edition.” Cengage Learning, 2012.

This is the first book (chinese version translated by Lei Duan et al.) I read on computation theory. The book is short and easy to follow. I personally think the content of this book may be enough for advanced algorithm design.

Oded Goldreich. “Computational Complexity: A Conceptual Perspective.” Cambridge University Press, 2008.

This is a longer book on computation complexity than the previous one. Although I read over this book once, I couldn’t fully understand it.

Approximation Algorithms

David P. Williamson and David B. Shmoys. “The Design of Approximation Algorithms.” Cambridge University Press, 2010.

This is the first book I read on approximation algorithms. I select these chapters to read: 1-5, 7-8, and 14-16. There are still 7 chapters I haven’t read. Hopefully, I can finish them during my Ph.D study.

Vijay V. Vazirani. “Approximation Algorithms.” Springer Science & Business Media, 2013.

This book introduces many classic problems and I really like this book. When reading this book, my friends and I have made up some slides for some of the chapters, including overview, 1, 2, 3, 4, 5, 8, 9, 10, 12. I really appreciate with their helps.

Randomized Algorithms

Michael Mitzenmacher, Eli Upfal. “Probability and Computing: Randomized Algorithms and Probabilistic Analysis.” Cambridge University Press, 2005

This is very nice textbook on randomized algorithm and probability anlaysis. When reading this book, my friends and I have made up some slides for some of the chapters, including 1, 2, 3, 4, 5. This book has a new edition which has more materials on learning theory. Although I have bought the new edition, I did not read these materials.

Rajeev Motani and Prabhakar Raghavan. “Randomized Algorithms.” Cambridge University Press, 1995.

This is a very detailed book on randomized algorithms. The book has two parts: (1) tools and techniques, (2) applications. I have only read the first part.

More Specific

Allan Borodin, Ran El-Yaniv. “Online computation and competitive analysis.” Cambridge University Press, 1998.

This is a very classic book on online algorithm design. Whenever I am struggling in online problems, I often find good directions from this book. Recently, I have been motivated by the chapter 5 in this book.

Sariel Har-Peled. “Geometric Approximation Algorithms.” American Mathematical Society, 2011.

This is a very good book on geometric approximation algorithms. Some of the chapters are really helpful for me to study spatial databases.

Tim Roughgarden. “Twenty Lectures on Algorithmic Game Theory.” Cambridge University Press, 2016.

This book teaches me the basic concepts and theoretical results in game theory. When reading this books, my friends and I have made up some slides for some of the lectures, including 1, 2, 3, 4, 5, 6, 9, 10, 11. This book has a course website on Tim Roughgarden’s homepage.

Tim Roughgarden. “Beyond the Worst-Case Analysis of Algorithms.” Cambridge University Press, 2020.

For year 2021, I plan to read this new book edited by Tim Roughgarden. I found this book is very interesting, since many recent STOC/FOCS papers have discussed this topic, “beyond the worst-case analysis”. One of my recent submissions also studies this issue.

Databases

Nikos Mamoulis. “Spatial Data Management.” Morgan & Claypool Publishers, 2011.

This is a very nice book on spatial databases. I have read it over and I promise it won’t take too long time. It elaborates many fundamental challenges and representative solutions in spatial databases.

Serge Abiteboul, Richard Hull, Victor Vianu. “Foundations of Databases.” Addison-Wesley, 1995.

Although I am reading this book in a very slow speed, it teaches me a lot about the database theory and the mechanisms/principles behind a DBMS.

Graham Cormode, Ke Yi. “Small Summaries for Big Data.” Cambridge University Press, 2020.

This is a new book that I am currently reading. The draft of this book can be accessed from the authors’ webpage.