Design and Analysis of Algorithms

From Wikiversity
Jump to navigation Jump to search
Educational level: this is a tertiary (university) resource.
Completion status: this resource is ~25% complete.
Subject classification: this is a mathematics resource.
Subject classification: this is an information technology resource.
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.

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?

Course Outline[edit | edit source]

Introduction[edit | edit source]

Mathematical Foundations[edit | edit source]

Sorting[edit | edit source]

Extra videos


Divide and Conquer Methods[edit | edit source]

Greedy Methods[edit | edit source]

Extra videos


Pattern Matching[edit | edit source]

Backtracking[edit | edit source]

Graph Algorithms[edit | edit source]

Dynamic Programming[edit | edit source]

Extra videos


NP-Completeness[edit | edit source]

Extra videos


Approximation algorithms[edit | edit source]

Maximum Bipartite Matching[edit | edit source]

Problems Sets[edit | edit source]

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

Exams[edit | edit source]

Textbooks[edit | edit source]

Free textbooks:

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

Supplementary Materials[edit | edit source]

Related Websites[edit | edit source]

References[edit | edit source]

  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 also[edit | edit source]

Retrieved from "https://en.wikiversity.org/w/index.php?title=Design_and_Analysis_of_Algorithms&oldid=2193952"