Saved searches
Use saved searches to filter your results more quickly
Cancel Create saved search
Sign up Reseting focus
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.
Solutions to exercises and problems from "Introduction to Algorithms", Fourth Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein
License
Notifications You must be signed in to change notification settings
wojtask/clrs4e-solutions
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
Go to file
Last commit message
Last commit date
Latest commit
History
View all files
Repository files navigation
Introduction to Algorithms, Fourth Edition — solutions to exercises and problems
Overview
- 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.
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 |
|---|
|
|
|
|
|
|
|
|
Roadmap
- 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.
- 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).
Building
To compile the project locally you need a relatively fresh LaTeX distro, like TeX Live 2023 or newer. Using 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 util/install_fonts.sh && sudo util/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
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!
About
Solutions to exercises and problems from "Introduction to Algorithms", Fourth Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein
