1.1. Data and Algorithm Analysis¶
1.1.1. Introduction¶
This eTextbook is intended for a senior-level course in Data and Algorithm Analysis, or Theory of Algorithms.
1.1.1.1. 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 \(\Theta\) notations.
Basic data structures and algorithms including lists, search structures such as BSTs, sorting algorithms, heaps, hashing, and basic graph algorithms.
1.1.1.2. 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.
A little bit of computability theory as a bonus.
1.1.1.3. Process¶
The primary work in this course will come from the weekly homework sets. They will typically consist of two or three problems. You should expect that a lot of them will be fairly hard.
The homeworks are designed assuming that you will work with a partner to complete the homework (but it is not required that you do work with a partner). 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 of your partner’s proposed solution is a key contribution, especially if you (correctly) point out errors, or verify that the answer makes sense. Recognizing that an answer is no good, or incomplete, is crucial to succeeding in this class.
