"That fondness for science, ... that affability and condescension which God shows to the learned, that promptitude with which he protects and supports them in the elucidation of obscurities and in the removal of difficulties, has encouraged me to compose a short work on calculating by al-jabr and al-muqabala , confining it to what is easiest and most useful in arithmetic."

Abu Ja'far Muhammad ibn Musa Al-Khwarizmi
[Born: about 780 in Baghdad (now in Iraq). Died: about 850]

[al-jabr means "restoring", referring to the process of moving a subtracted quantity to the other side of an equation; al-muqabala is "comparing" and refers to subtracting equal quantities from both sides of an equation.]

Compilers  | Computational Geometry  | Computer Architecture | Computer Science
Engineering/Technology | Java | Operating Systems | Parallel Computing 

Algorithms Lecture Notes

1. Introduction
2. Mathematics for Algorithmic
• Sets
  
• Functions and Relations
  
• Vectors and Matrices
• Linear Inequalities and Linear Equations
3. Greedy Algorithms
   • Knapsack Problem
     • O-I Knapsack
     • Fractional Knapsack
   • Activity Selection Problem
   • Huffman's Codes
   • Minimum Spanning Tree
   • Kruskal's Algorithm
   • Prim's Algorithm
   • Dijkstra's Algorithm
4. Divide & Conquer Algorithms
5. Dynamic Programming
   • Matrix-chain Multiplication
   • Knapsack Problem DP Solution
   • Activity Selection Problem DP Solution
6. Amortized Analysis
   • Aggregate Method
   • Accounting Method
   • Potential Method
   • Dynamic Table
7. Hash Table
8. Binary Search Tree
   
9. Graph Algorithms
   • Breadth First Search (BFS)
   • Depth First Search (DFS)
   • Topological Sort
   • Strongly Connected Components
   • Euler Tour
   • Generic Minimum Spanning Tree
   • Kruskal's Algorithm
   • Prim's Algorithm
   • Single Source Shortest Path
     • Dijkstra's Algorithm
     • Bellman-Ford Algorithm
10. String Matching
    • Naïve String Matching
    • Knuth-Morris-Pratt Algorithm
    • Boyer-Moore Algorithm
11. Sorting
    • Bubble Sort
    • Insertion Sort
    • Selection Sort
    • Shell Sort
    • Heap Sort
    • Merge Sort
    • Quick Sort
12. Linear-Time Sorting
    • Counting Sort
    • Radix Sort
    • Bucket Sort
13. Computational Geometry
14. Computational Complexity
    • Information-Theoretic Argument
    • Adversary Argument
    • NP-Completeness And Reduction
15. Approximate Algorithms
    • Vertex Cover
    • The Traveling Salesman Problem
16. Linear Programming
17. Appendix
    1. Parabola
    2. Tangent
18. Codes
19. References

Algorithm Home Page
Dictionary of Algorithms & Data Structures --  NIST  
Dictionary of Algorithms & Data Structures -- FOLDOC
On-line Encyclopedia of Integer Sequences
Glossary (Design & Analysis of Algorithms).
Algorithms and Data Structures Books 
Books by Don Knuth (and links to papers)

Books

• Algorithm Design - Foundations, Analysis & Internet Examples by Michael T. Goodrich and Roberto Tamassia
• Data Structures and Algorithms in Java by Michael T. Goodrich and Roberto Tamassia
• Data Structures and Algorithms in C++ by Michael T. Goodrich, Roberto Tamassia and David M. Mount
• Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein
  • Online Learning Center  -- CLR chapters overview and PowerPoint slides

Journals

• Algorithmica: Home | Electronic Access via OhioLink (Dec.98 -Present) | Print Issues at Math lib.
• Journal of Algorithms: Home | Electronic Access via OhioLink (Jan.93 - Present)
• Journal of Graph Algorithms & Applications -- An electronic journal available via WWW. All papers freely available in PostScript and PDF.

Links

• Algorithmist, The -- dedicated to anything algorithms - from the practical realm, to the theoretical realm.
• Algorithms Course Material on the Net
• Algorithms in the Real World  course by Guy E. Blelloch
• Algorithmic Solutions (formerly LEDA Library) -- a library of the data types and algorithms ( number types and linear algebra, basic data types, dictionaries, graphs, geometry, graphics).
• Analysis of Algorithms Lectures at Princeton -- Applets & Demos based on CLR.
• Collected Algorithms(CALG) of the ACM
• Complete Collection of Algorithm Animations (CCAA)
• Data Structures And Number Systems -- by Brian Brown.
• Function Calculator by Xiao Gang
• FAQ - Com.graphics.algorithms -- maintained by Joseph O'Rourke
• Game Theory Net
• Grail Project -- A symbolic computation environment for finite-state machines, regular expressions, and finite languages.
• Java Applets Center by R.Mukundan
• Lecture Notes by Diane Cook
• Lecture Notes  for Graduate Algorithms by Samir Khuller
• Maze classification and algorithms -- A short description of mazes and how to create them. Definition of different mazetypes and their algorithms.
• Priority Queues -- Electronic bibliography on priority queues (heaps). Links to downloadable reports, researchers' home pages, and software.
• Softpanorama Vitual Library /Algorithms
• Ternary Search Trees -- Algorithm for search. PDF file and examples in C.
• Traveling Salesman -- bibliography and software links.

Computatability

• Algorithms and Complexity  -- A downloadable textbook by Herbert S. Wilf.
• Blackbox - a SAT Technology Planning System -- Blackbox is a planning system that works by converting problems specified in STRIPS notation into Boolean satisfiability problems, and then solving the problems with a variety of state-of-the-art satisfiability engines.
• Bibliographic Database for Computability Theory -- Extensive bibliography on computability and recursion theory, maintained by Peter Cholak.
• Compendium of NP Optimization Problems  -- This is a preliminary version of the catalog of NP optimization problems.
• Computability and Complexity -- An online course on complexity.
• Computational Complexity and Statistical Physics  -- Santa Fe, New Mexico, USA; 4--6 September 2001.
• Complexity International -- journal for scientific papers dealing with any area of complex systems research.
• Computability Theory  -- Directory of researchers working in computability theory, and list of open problems.
• ECCC - Electronic Colloquium on Computational Complexity  -- The Electronic Colloquium on Computational Complexity is a new forum for the rapid and widespread interchange of ideas, techniques, and research in computational complexity. The Electronic Colloquium on Computational Complexity (ECCC) welcomes papers, short notes and surveys with relevance to the theory of computation.
• Hypercomputation Research Network -- The study of computation beyond that defined by the Turing machine, also known as super-Turing, non-standard or non-recursive computation. Links to people, resources and discussions.
• IEEE Conference on Computational Complexity -- This conference started as "Structure in Complexity Theory" in 1986. It recently acquired the new name "Conference on Computational Complexity", which was used for the first time in 1996. CTI, DePaul University, Chicago IL; 18--21 June 2001.
• SAT Live! -- A collection of up-to-date links about the satisfiability problem (solvers, benchmarks, articles). A discussion forum is available as well.
• Roberto Bayardo's Resources -- Includes the relsat SAT solver and related papers.
• Problem Solving Environments Home Page -- This site contains information about Problem Solving Environments (PSEs), research, publications, and information on topics related to PSEs.
• SATLIB - The Satisfiability Library  -- A collection of benchmark problems, solvers, and tools. One strong motivation for creating SATLIB is to provide a uniform test-bed for SAT solvers as well as a site for collecting SAT problem instances, algorithms, and empirical characterisations of the algorithms' performance.
• Stas Busygin's NP-Completeness Page  -- A proposal for solving NP-hard problems.

Quantum Computing

• Centre for Quantum Computation -- Based at Oxford University. Well designed site, with a large amount of information available.
• D-Wave Systems, Inc. -- D-Wave Systems (dwavesys.com) is a portal to the state of the art in the design of quantum computers, operating systems, algorithms, hardware, superconductors, and quantum physics.
• id Quantique -- Site Of id Quantique, Inc. Products include a quantum random number generator,and a quantum cryptography system.
• MagicQ Technologies Inc. -- The home site of the first start up company devoted entirely to quantum computing. No patents or products to date, but of interest by virtue of being first off the block.
• Quantum Architecture Research Center -- The home page of a team formed by Frederic Chong, Isaac Chuang, and John Kubiatowicz, the three top experimentalists in quantum computing.
• Quantum Computation Archive This site contains both technical papers and links to QC reports in the media.
• Quantum Computer Emulator (QCE) -- A Windows based simulator of quantum computer hardware. Provides an environment to execute quantum algorithms under realistic experimental conditions.
• Quantum Computer Physics Laboratory of IPT Russian Academy of Sciences -- "Quantum Computer" seminar program. Staff, contact info, research papers. 
• Quantum Computing At The Max Plank Institute -- Provides an overview of quantum computer related research taking place at the Max Plank Institute. The primary focus is ion trap based computing. Selected reprints are available.
• Quantum Computing with Electron Spins in Quantum Dots -- A detailled study of using electron spins for quantum computation. Several possible implementations are discussed.
• Quantum Informatics at the University of Aarhus -- Performs research on quantum computing with an emphasis on quantum cryptography.

Algorithms

• Graham's scan (Convex Hull Algorithm) (Applet)
• Line Sweeping Algorithm  (Applet)
• Max Flow  (Applet)
• SkipList  (Applet)
• Stable Marriage (Applet)

Graph Algorithms

Societies and Organizations

• Numerical Algorithms Group (NAG)
  

Geometry

• Line Sweeping Algorithm
• Graham Scan and Gift Wrapping
• Graham's Scan (Convex Hull Algorithm)
• Qhull-- The QuickHull Algorithm.

There is no place like Home