NOTES ON
DESIGN AND ANALYSIS OF COMPUTER ALGORITHMS

[Return to the Parent Directory]


INTRODUCTION

Introduce the course and administrivia.


ASYMPTOTIC ANALYSIS

Focus on growth rates, bounds, and the difference between worst-case, average-case, and amortized analysis.


RECURRENCES

It is not always clear the complexity of an algorithm. Learn how forming recurrences can part the fog.


DIVIDE-AND-CONQUER

Break problems into smaller subproblems, solve them recursively, and combine the results with a simple merge step.


DYNAMIC PROGRAMMING

Record overlapping subproblems once, then reuse the stored results instead of recomputing them.


GREEDY METHODS

Choose locally optimal steps only when the exchange argument or cut property makes the choice safe.


MATROIDS

See a beautiful combinatorial theory perfectly describes many situations where the greedy method does yield optimal solutions.


GRAPHS

Learn about traversals, shortest-paths, and spanning-tree techniques, but keep them separate so the structure of the problem stays visible.


NETWORK FLOWS

Model problems as a graph having a flow coursing through it.


NP-COMPLETENESS

Use reductions to compare problem difficulty and keep the boundary between tractable and intractable problems clear.


RANDOMISED ALGORITHMS

Describe expected performance, probability of failure, and the role randomness plays in simplifying the analysis.



[Return to the Parent Directory]

pwd: /~wtd/TEACHING/grad_algos_notes.html