search

wojtask / clrs4e-solutions

Solutions to exercises and problems from "Introduction to Algorithms", Fourth Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein
Creative Commons Attribution 4.0 International
236 stars 37 forks source link
algorithms clrs data-structures solutions

readme

Introduction to Algorithms, Fourth Edition — solutions to exercises and problems

Build PDF

Overview

The goal of this project is to provide solutions to all exercises and problems from Introduction to Algorithms, Fourth Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. My intention is to ensure, first and foremost, the rock solid correctness and completeness of the provided content, its technical elegance, as well as its consistency with the textbook material. In order to achieve such reliability, I put a lot of effort into evolving and revising the solutions, not only in terms of accuracy and content-related correctness, but also in terms of terminology, wording, and typography. I also pay attention to providing optimal algorithms, which are then implemented and thoroughly tested, and to illustrate operations and examples with accurate pictures, consistent with the style of the textbook.

It should be noted that the textbook authors also provide the official Selected Solutions, which cover about 7% of all exercises and problems. Additionally, other researchers publicly host their solutions on the web, though majority of those that I found are for the third edition of the textbook:

However, none of the above sources cover all exercises, especially when compared to the fourth edition that adds a significant number of new exercises. Also, I noticed that some solutions are not of the highest quality, with defects ranging from incorrectness or incompleteness to the lack of technical elegance. Nevertheless, these pieces of work were sources of inspiration for me, and showed different approaches and perspectives. When borrowing on the ideas presented there, I always aimed to rework the solutions by introducing necessary fixes and improvements, and refine to improve consistency with the book.

The solutions here often refer to the material presented in the textbook, so familiarity on at least the corresponding chapter is required. In many solutions, you will also find references to other tasks, especially when a given task uses the result of another in its own solution. In general, later solutions sometimes rely on the earlier ones by referencing the relevant exercises. Thus, in early chapters one can observe a somewhat greater focus on details, and in later chapters more cross-references to exercises where those details have already been discussed.

I keep an eye on errors or inaccuracies in exercises and problems or the material they directly rely on, and highlight them in brief notes just before the solution of the affected exercise. At the same time I refer to the textbook's errata — if it includes a certain correction, I assume that the bug has already been fixed in a subsequent printing.

As I stressed earlier, I pay special attention to ensuring the correctness of the algorithms and data structures operations. To maximize my confidence, I implement and test each pseudocode or algorithm description that I provide in the solutions, as well as those that are provided in the textbook. I chose Python as a programming language, because of its popularity and its syntax similar to that used in pseudocodes. The counterpart project with implementations is available here.

The list of provided algorithms.

Detailed project's conventions.

History

The origins of the project date back to 2005, when I started solving exercises by pen and paper, while studying algorithms as a preparation for participating in the Polish Olympiad in Informatics. I was relying on the Polish translation of the textbook's second edition, titled Wprowadzenie do algorytmów, and my solutions were in Polish as well. In 2009 I started rewriting them in LaTeX. The document has evolved since then, with changes involving numerous fixes, improved page layout and styling, as well as open sourcing it on GitHub as CormenSol. At the beginning the pictures were drawn in MetaPost, before having been rewritten to PGF/TikZ in 2016. In 2012 I started implementing algorithms, first in C++, then in Java, before finally settling on Python in 2017, and I open sourced the implementations as CormenPy. Since initiating the project, the textbook got updated to the third edition in 2009, then to fourth edition in 2022. Having solved Chapters 1-17 and Appendices A-C from the — now outdated — second edition, I decided to freeze both CormenSol and CormenPy, and shift my attention to adapt the solutions for the fourth edition, while translating them to English — the process I refer to as migration.

The work on the current project began on January 1, 2023.

Progress

Part I Part II Part III Part IV Part V Part VI Part VII Part VIII
Chapter 1
Chapter 2
Chapter 3
Chapter 4
Chapter 5 		Chapter 6
Chapter 7
Chapter 8
Chapter 9 		Chapter 10
Chapter 11
Chapter 12
Chapter 13 		Chapter 14
Chapter 15
Chapter 16 		Chapter 17
Chapter 18
Chapter 19 		Chapter 20
Chapter 21
Chapter 22
Chapter 23
Chapter 24
Chapter 25 		Chapter 26
Chapter 27
Chapter 28
Chapter 29
Chapter 30
Chapter 31
Chapter 32
Chapter 33
Chapter 34
Chapter 35 		Appendix A
Appendix B
Appendix C
Appendix D

Roadmap

Building

To compile the project locally at least TeX Live 2023 is required. Older versions may produce an error with unrecognized option twoside of the package fancyhdr. The support of this option was added in fancyhdr v4.1 dated 2022-11-09. As a workaround, the option can be manually removed before compiling the document. This will change the way page headers are displayed; they will have the same format on left-hand pages and right-hand pages, but it shouldn't have a dramatic effect on the output.

On Debian/Ubuntu the minimal required set of TeX Live packages can be installed with:

sudo apt install texlive-pstricks texlive-latex-extra texlive-fonts-extra latexmk

Additionally, you need to install the MathTime Professional II Lite fonts. Since the fonts are not available in the standard TeX Live distribution, you will need to install them using the provided script:

chmod +x scripts/install_fonts.sh && sudo scripts/install_fonts.sh

Once the environment has been prepared, you can compile the document to PDF by running the following command:

latexmk -pdf -file-line-error -halt-on-error -interaction=nonstopmode clrs4e-solutions.tex

Using other LaTeX distributions or other operating systems may require adapting the above commands or performing additional actions before compiling the document.

Contributions

Again, a significant effort has been made to ensure that each solution is thoroughly checked. However, if you have found an error of any kind, or you can improve an existing solution in any way, I will be grateful for your feedback or help. Each exercise and each subproblem has its own issue in this repository, named and categorized appropriately. Please avoid duplicating these issues, rather search for the right one, and leave a comment, or even better — create a pull request with your suggestions. Authors of significant contributions will be credited in the document.

Together let's make this the most complete, reliable and consistent set of solutions to the iconic CLRS!

— Krzysztof Wojtas