Design and Analysis of Algorithms

Sciences humaines.svg Educational level: this is a tertiary (university) resource.
Progress-0250.svg Completion status: this resource is ~25% complete.
Nuvola apps edu mathematics-p.svg Subject classification: this is a mathematics resource.

Donald Knuth lists, in the preface of The Art of Computer Programming Vol 3, the following as the important questions of design and analysis of algorithms[1]:

  • How are good algorithms discovered?
  • How can given algorithms and programs be improved?
  • How can the efficiency of algorithms be analyzed mathematically?
  • How can a person chose rationally between different algorithms for the same task?
  • In what senses can algorithms be proved "best possible"?
  • How does the theory of computing interact with practical considerations?
  • How can external memories like tapes, drums, or disks be used efficiently with large databases?
Edsger Dijkstra invented the shortest-path algorithm that bears his name. He also made contributions to formal specification and verification, algorithm design, programming languages, program design, operating systems, and distributed processing. Much of his writing is free to access at the E.W. Dijkstra Archive.

Course OutlineEdit

IntroductionEdit

Mathematical FoundationsEdit

SortingEdit


Divide and Conquer MethodsEdit

Greedy MethodsEdit


Pattern MatchingEdit

BacktrackingEdit

Graph AlgorithmsEdit

Dynamic ProgrammingEdit


NP-CompletenessEdit


Approximation algorithmsEdit

Maximum Bipartite MatchingEdit

Problems SetsEdit

solve the recurrence equuation for t(n)=2t(n-1)+n2^n+n^2

ExamsEdit

TextbooksEdit

Free textbooks:

  • Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani

Supplementary MaterialsEdit

Related WebsitesEdit

ReferencesEdit

  1. Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Preface, pp.v.

See alsoEdit