.. raw:: html
.. _AAIntro:
.. raw:: html
.. |--| unicode:: U+2013 .. en dash
.. |---| unicode:: U+2014 .. em dash, trimming surrounding whitespace
:trim:
.. 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::
:author: Cliff Shaffer
:requires:
:satisfies: DSA Introduction
:topic: Introduction
Data and Algorithm Analysis
===========================
Introduction
------------
This eTextbook is intended for a senior-level course in Data and
Algorithm Analysis, or 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
~~~~~~~~~~~~~~~
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.
* A little bit of computability theory as a bonus.
Process
~~~~~~~
The primary work in this course will come from the weekly homework
sets.
They will typically consist of three problems.
You should expect that a lot of them will be fairly hard.
The intention of the course design is that you will work with a
partner on the homework.
Understanding this course content is hard.
Figuring out the problem solutions is intended to be hard.
This works best if you can bounce ideas off of someone else, and
actively work together toward a final solution.
If nothing else, being a skeptical reviewer is a key contribution.
Recognizing that an answer is no good, or incomplete, is crucial to
succeeding in this class.