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:
- solutions by Michelle Bodnar and Andrew Lohr,
- solutions by Stefan Kanev,
- solutions by Don R. Walsh,
- crowdsourced solutions coordinated by Peng-Yu Chen,
- the textbook's page on Quizlet.
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.
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.
| Part I | Part II | Part III | Part IV | Part V | Part VI | Part VII | Part VIII |
|---|---|---|---|---|---|---|---|
|
|
|
|
|
|
|
|
- Add project's documentation (you are reading it now), create issues and milestones, setup document's stub, suggest page layout and styling.
- Migrate the CormenSol solutions from Appendices A-C. Add solutions to the modified and new exercises and problems along the way.
- Add solutions to Appendix D, previously missing in the second edition, completing Part VIII (release 0.1).
- Migrate the CormenSol solutions from Chapters 1-17 and the corresponding CormenPy implementations.
Add solutions and implementations to modified and new exercises and problems along the way.
- Complete Part I (release 0.2).
- Complete Part II (release 0.3).
- Complete Part III (release 0.4).
- Complete Part IV (release 0.5).
- Complete Chapter 17 from Part V.
- Add solutions and implementations to Chapters 18-35.
- Complete Part V (release 0.6).
- Complete Part VI (release 0.7).
- Complete selected chapters from Part VII (release 0.8).
- Complete Part VII (release 0.9).
- Finalize the document (release 1.0).
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 latexmkAdditionally, 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.shOnce 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.texUsing other LaTeX distributions or other operating systems may require adapting the above commands or performing additional actions before compiling the document.
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