.. This file is part of the OpenDSA eTextbook project. See
.. http://opendsa.org for more details.
.. Copyright (c) 2012-2020 by the OpenDSA Project Contributors, and
.. distributed under an MIT open source license.

.. avmetadata::
   :title: Theory of Algorithms
   :author: Cliff Shaffer
   :institution: Virginia Tech
   :requires:
   :satisfies: DSA Introduction
   :topic: Introduction
   :keyword: Algorithm Analysis
   :naturallanguage: en
   :programminglanguage: N/A
   :description: Introductory module for a course on Theory of Algorithms


Theory of Algorithms
====================

Introduction
------------

This eTextbook is intended for a graduate-level course in Theory of Algorithms.


Prerequisites
~~~~~~~~~~~~~

This course assumes that you already have sufficient background in a
number of Computer Science topics 

You should have had a course in Discrete Math, covering at least the
following:

* Basic proof techniques like proof by contradition and induction.
* Basic techniques for solving summations and recurrence relations
* Set theory and relations

You should have had a course in Data Structures to cover at least the
following:

* Basic algorithm analysis, including big-oh, big-Omega, and
  :math:`\Theta` notations.
* Basic data structures and algorithms including lists, search
  structures such as BSTs, sorting algorithms, heaps, hashing, and
  basic graph algorithms.


What we will do
~~~~~~~~~~~~~~~

During this course, we will talk about problems and algorithms that
are probably new to you.
But that is not really the focus for the course.
A lot of the time we will be working to understand new techniques for
analyzing algorithms and problems.
So we get a lot of cases where we see an "obvious" algorithm, and work
hard to prove that it is "best".
Many of the problems and algorithms picked to study are choosen
deliberately to expose new ways to do analysis.

Major topics/goals for this course include:

* Getting a good understanding of upper and (especially) lower bounds
  for an algorithm or problem.
* Lower bounds proofs.
* Analysis techniques, including solving a lot of summations and
  recurrence relations.
* Reductions, most importantly NP-completeness theory.
* Some graph algorithms.