Algorithmic reasoning: choose a text and justify an optimization
An algorithm choice needs a model, a correctness argument and a resource bound. This route uses a free proof-oriented text, a broad pseudocode reference and a practical modeling companion. Choose one spine; use the others to answer a specific difficulty rather than collecting three parallel reading assignments.
Study route and exercise: University Reading List editorial project. How we curate · Sources checked:
Scope and responsibility
This is an undergraduate design-and-analysis route after basic programming, recursion, data structures and discrete mathematics. Erickson explicitly assumes those foundations; free access does not make it a first coding book. The scheduling data and solutions below were invented for this guide, not taken from a publisher exercise or tested in a workplace.
Choose your starting point
I can program but need to justify designs
Use Erickson as the free spine once induction and elementary data structures are comfortable. Write the invariant or recurrence before translating it into code.
My course specifies CLRS
Follow the assigned fourth-edition sections and pseudocode conventions. Use the selected design chapters first; its breadth is a reference opportunity, not a requirement to read 1,312 pages in sequence.
I struggle to recognize the underlying problem
Use Skiena to name a problem model and inspect candidate approaches, then return to a proof-oriented explanation when an implementation story does not establish correctness.
Compare the three books
Algorithms
Jeff Erickson · Edition: 1 · 2019
Free proof-and-design spine
- Choose it when
- You can follow induction and want to construct arguments, counterexamples and recurrences.
- Use another route when
- You still need a first treatment of stacks, hash tables or programming syntax.
- Selected reading
- 2019 edition: chapters 1–4, then selected graph chapters 5–8.
- Limits and trade-offs
- The author explicitly lists omitted prerequisite data structures and does not supply exercise solutions on request. Open book access is distinct from an answer key.
Try before choosing
After chapters 3–4, explain why earliest finishing can fail when interval rewards differ; use the five-job packet below rather than a textbook question.
Check your work: Give a feasible greedy schedule, compute its reward and exhibit a better feasible schedule. A larger number of jobs is not the stated objective.
Introduction to Algorithms
Thomas H. Cormen et al. · Edition: 4 · 2022
Broad fourth-edition reference
- Choose it when
- A syllabus requires CLRS or you need one consistent pseudocode treatment across many techniques.
- Use another route when
- You need a short first pass and cannot select chapters or establish preparation.
- Selected reading
- Use the named Dynamic Programming and Greedy Algorithms chapters, with analysis/data-structure review as needed; match the fourth-edition contents in your copy.
- Limits and trade-offs
- The selected hardcover is 2022, ISBN 9780262046305. Restricted instructor supplements are not a public solution entitlement; a print identifier does not include every digital product.
Try before choosing
State one optimization subproblem in words before matching it to a CLRS recurrence. Specify what information an optimal continuation can ignore.
Check your work: Your state description determines the alternatives and base case. Merely recognizing the notation does not justify optimal substructure.
The Algorithm Design Manual
Steven S. Skiena · Edition: 3 · 2020
Problem-modeling companion
- Choose it when
- You want to translate an application into a known combinatorial problem and compare implementation options.
- Use another route when
- You need its catalogue alone to replace proofs or to guarantee that a community solution is correct.
- Selected reading
- Third edition: practical-design chapters, especially 10 on dynamic programming; browse catalogue entries only after defining the model.
- Limits and trade-offs
- The author-hosted solution wiki warns that community answers are not certified. Use it as an argument to check, not an authority that settles a disputed result.
Try before choosing
Write two descriptions of the same booking problem: one as a story, one as weighted intervals with compatibility and objective.
Check your work: Every story condition either appears in the formal model or is explicitly excluded. A familiar problem name is not permission to discard a constraint.
Check your preparation
Can I separate feasibility from optimality?
Feasibility means satisfying every constraint. Optimality compares the objective with every feasible alternative; one attractive example proves neither.
What does induction buy a recurrence?
It connects a smaller solved subproblem to the current optimum. The argument must show that the chosen cases cover all feasible optimal solutions.
What should a running-time claim state?
Define n, the input representation, and the work counted. Sorting, predecessor computation, table filling and reconstruction are separate costs.
Six steps with a concrete output
Outputs marked ready: 0 / 6
These are your own study marks, not an assessment. They are not sent to this site.
-
Write the model
Selected reading: Erickson chapter 0 and Skiena’s modeling discussion.
Make this: Specify fixed start/finish times, half-open intervals, rewards, one resource and a sum-of-rewards objective.
Check your work: Two jobs touching at an endpoint are compatible in this base model; no hidden travel time or rescheduling is assumed.
-
Break an unjustified shortcut
Selected reading: Erickson chapter 4 and the selected greedy discussion in CLRS.
Make this: Run earliest finish on the packet and compare its reward with a feasible counterexample.
Check your work: Show the actual selected job IDs. A counterexample refutes a universal claim; it does not show every greedy strategy fails.
-
Define the state
Selected reading: Erickson chapter 3 and the named CLRS dynamic-programming chapter.
Make this: Sort by finish time and define V(j) and p(j) in complete sentences.
Check your work: V(j) covers the first j finish-ordered jobs; p(j) is the last earlier job compatible with j, or zero.
-
Fill and explain the table
Selected reading: Same dynamic-programming selections.
Make this: Compute the two alternatives at every row, retain a predecessor and reconstruct a schedule.
Check your work: The recurrence considers excluding j or including j with an optimal compatible prefix. Explain why there is no third structural case.
-
Test a changed constraint
Selected reading: Skiena chapter 10 plus the follow-up packet.
Make this: Add the stated turnaround gap and recompute compatibility before reusing the table.
Check your work: A changed p array can invalidate an old optimum even though rewards and the recurrence’s outer form remain unchanged.
-
Report an auditable result
Selected reading: Return to the book that resolves your weakest step.
Make this: Submit the model, counterexample, table, reconstructed schedule, cost analysis and one boundary test.
Check your work: Another reader can reproduce the reward and feasibility; timing one tiny program is not an asymptotic analysis.
Worked exercise
Original packet: earliest finish does not maximize reward
Five invented jobs have (start, finish, reward): a=(0,3,5), b=(3,5,4), c=(0,5,12), d=(5,7,3), e=(4,8,11). One resource can process nonoverlapping jobs. Find the maximum reward and compare earliest finish.
Assumptions
Intervals are half-open, so an ending job can be followed immediately by another. Times are fixed, jobs are indivisible, rewards add and all rewards are nonnegative. No setup gap, travel or uncertainty is included. Break the equal-finish tie by b before c; this affects table order, not the optimum.
- Earliest finish selects a, b, d for reward 5+4+3=12. The feasible pair a, e earns 16, so this particular greedy rule does not solve the weighted objective.
- In finish order a, b, c, d, e, predecessor indices are p=[0,1,0,3,1]. Set V(0)=0 and V(j)=max(V(j−1), reward(j)+V(p(j))). Excluding and including the final job partition the possibilities.
- The table is V=[0,5,9,12,15,16]. The last row takes e and predecessor a; reconstructed reward is 11+5=16.
- A sort plus binary-search predecessors can take O(n log n), followed by O(n) table filling and reconstruction with O(n) storage. The tiny five-job trace checks this instance; the include/exclude argument supplies the general reasoning.
Answer and interpretation
The maximum reward is 16, achieved by a and e. The greedy three-job schedule earns 12. Maximizing count and maximizing reward are different objectives.
Test the result
Enumerate all 32 subsets of this five-job packet independently, rejecting incompatible pairs. Recover the same optimum, and verify every reconstructed endpoint rather than trusting a table value alone.
Change an assumption
Follow-up: a mandatory gap changes compatibility
Keep the five jobs and rewards, but require at least two time units between the finish of one selected job and the start of the next. The gap is only between selected jobs, not after the last one. Times cannot shift. Recompute the optimum.
- Compatibility now requires finish(i)+2≤start(j). In the same order, p=[0,0,0,1,0]; a can precede d, but cannot precede b or e.
- The new table is [0,5,5,12,12,12]. Choosing c alone earns 12. The old pair a, e is infeasible because 3+2>4.
Answer and interpretation
The new optimum is 12, attained by c alone. Keep the recurrence but rebuild the compatibility data; subtracting a generic penalty from the old reward would model another problem.
Test the result
Enumerate the subsets again with the changed predicate. The one-job solution needs no final gap. Explain why the old optimum is a bound from a relaxed model, not a feasible answer here.
Common mistakes
Pseudocode as proof
A program that returns the desired value on this packet has not established correctness for every input. Separate the general argument from finite tests.
A catalogue entry as a model
Real constraints such as setup time can invalidate a familiar reduction. State excluded features before selecting an algorithm.
Big-O without accounting
Do not call the whole implementation linear after ignoring sorting or an O(n²) predecessor scan. State which implementation your bound describes.
Before moving on
- I can state the objective and every compatibility rule.
- I can defend the recurrence and reconstruct a feasible solution.
- I can change one assumption and identify which argument or data structure must change.
Sources and edition checks
Sources checked:
- Jeff Erickson: 2019 edition, prerequisites and chapter files
The author verifies the June 2019 edition, free text, prerequisites and chapter sequence. Trial tasks and packet data are this site’s work.
- MIT Press: Introduction to Algorithms, fourth edition
MIT Press confirms fourth edition, 2022 and separate print/eBook identifiers; instructor-only material is not promised to self-study readers.
- Springer: The Algorithm Design Manual, third edition
The publisher supports the practical-design/reference distinction. Editorial fit judgments are not claims of measured learning effectiveness.
- Author-hosted third-edition chapter and solution index
The author-hosted index locates dynamic programming and explicitly qualifies community answer reliability.
These are proposed study activities, not official course assignments or a claim that every book has been read cover to cover.