NOTES ON
DESIGN AND ANALYSIS OF COMPUTER ALGORITHMS

[Return to the Parent Directory]

INTRODUCTION

Introducing the course and its administrivia.

The notes herein are written in service to the course of CS 6363 at UTD on the Design and Analysis of Computer Algorithms. Much care is taken to its presentation: vocabulary terms are bolded, key ideas and notions are italicised, and definitions are underlined. The notes also offer periodic applications of the concepts so the student can realise the applicability of the lessons being engaged with.

Since these notes are written for a graduate course, certain methods, notations, algorithms, and background knowledge is assumed. For the brevity of these notes, we believe it best to simply refer the student to other sources who may better put the information should a need for them arise. Be certain to check back frequently for updates to this notes page. These notes are only meant for the student's own enrichment and are not to serve as a complete replacement to the lecture material or the textbook.

The word algorithm is a ubiquitous term in computer science. Algorithms help us solve problems—pure and simple. Simply put, an algorithm is an instruction on the content of a problem and the sequence of simple operations requisite to solve it. These instructions are to be carried precisely and to the dot. Despite its succinctness, the aforementioned definition benefits from being honed further. Specifically, thanks to Donald Knuth, an algorithm fulfills the certain properties of:

(1) Finiteness in its number of steps,
(2) Definitness in the determination of its steps, and
(3) Effecticeness in how basic the steps are.

Another more subtle demand of algorithm design is that the product is sufficiently general, applicable to not only a particular problem but also to the other problems of a similar ilk. This principle transcends this course. In an industrial setting, one's product is useless if the client can only use it for one of its problems. For instance, if a municipal healthcare client contracts with a company to design a new provider enrollment solution, it is natural that the product delivered would be able to accomodate all potential providers within a given jurisdiction. Otherwise, if the product can only sign up providers named "John Smith" and nobody else, then it is probable the company will no longer find a contract with that municipality.

A neat tool in the arsenal of algorithm design is the reduction. This should be a familiar term to those students familiar with Automata Theory, and the essence is the same: take a problem and show that it can be thought of as a different problem, which would mean both problems can be solved using one solution to either. This very concept is useful to an algorithms student because it allows a new, unfamiliar problem to be solvable by an algorithm for a familiar one by some sort of creative manipulation or rethinking.

In this course, we devote ourselves to the study of deterministic, exact algorithms which run sequentially and offline. That means we will mainly examine algorithms whose executions will produce the same output if given the same input (determinism). These algorithms have the input in full (offline) and execute commands in the order they are written (sequential). There are some others, such as those who take advantage of multicore architectures and can run instructions concurrently without issue (concurrent algorithms), those run on NP-hard problems that might not get us the exact answer but rather one within an appropriate factor (approximation algorithms), and even those whose information is not given or even known at the onset and are received in a stream (online algorithms). These more advanced algorithms and schemes are left to other courses.

Additionally, we make a further assumption on the scope of the algorithms we study. That is, we will be operating under the RAM Model of computation. Indeed, the "RAM" portion of that term is for "Random-Access". Henceforth, it is assumed that the essential operations of $+$, $-$, $/$, and $\times$ all have unit cost, as well as comparisons and any random access that may occur. Actually, the RAM model is one of four different types of abstract machines, a theoretical model to describe and analyse the functions of a computer. We refer the reader to [Wikipedia] for more.

ASYMPTOTIC ANALYSIS

Focus on growth rates, bounds, and the difference between worst-case, average-case, and amortized analysis.

Naturally, the study of algorithms requires a meter for comparison. Typically, such a meter is in truth a two-in-one tool that assesses the efficiency of an algorthm via the measures of time complexity and space complexity. Prior to that, however, the notion of efficiency must be more well-defined. Basically, there are many definitions for efficiency—perhaps how fast it runs or how much better an algorithm is as compared to a brute-force method. But, these are qualitative and hold little rigor.

A better definition of efficiency starts with understanding an elementary fact: if the inputs increase, the expectation is that the performance of an algorithm decreases; the extent to which it does is the interest of a good eye for algorithm design. Ergo, we can say that the input to and the performance of an algorithm are inversely proportional by a constant factor.

DEFINITION: EFFICIENCY. An algorithm is said to be efficient if for constants $c$ and $d$, every input of size $n$ is bounded by the expression $T(n) \leq cn^d, \forall n$.

With efficiency defined, we may turn now to the matter of properly defining the language of asymptotic analysis; "aymptotic" meaning that for functions $f(x)$ and $g(x)$, define the equivalence relation $f(x) \sim g(x), \text{ }x \rightarrow \infty$ iff $\lim_{x \rightarrow \infty} \frac{f(x)}{g(x)} = 1$. It is through the lens of asmptotic analysis that constant factors and lower-order terms can be ignored. Now, the orders of growth are defined for functions $f$ and $g$ from $\mathbb{R}$ to $\mathbb{R}$ and for constants $c$. The student should note that the bounds are the sets of functions for which the property defined herefrom holds.

DEFINITION: BIG-OH, THE UPPER BOUND. $f \in O(g)$ if
$\exists c > 0 \land \exists n_0 > 0 : \forall n \geq n_0, f(n) \leq c \cdot g(n)$. That would mean $O(g) = \{f : \exists c > 0 \land \exists n_0 > 0, 0 \leq f \leq c \cdot g \quad \forall n \geq n_0\}$.

DEFINITION: BIG-OMEGA, THE LOWER BOUND. $f \in \Omega(g)$ if
$\exists c > 0 \land \exists n_0 : \forall n \geq n_0, f(n) \geq c \cdot g(n)$. That would mean $\Omega(g) = \{f : \exists c > 0 \land \exists n_0 > 0, 0 \leq c \cdot g \leq f \quad \forall n \geq n_0\}$.

DEFINITION: BIG-THETA, THE TIGHT BOUND. $f \in \Theta(g)$ if
$\exists c > 0 \land \exists n_0 : \forall n \geq n_0, f(n) \leq c \cdot g(n) \land f(n) \geq c \cdot g(n)$. Alternatively, $f \in O(g) \land f \in \Omega(g)$.

DEFINITION: LITTLE-OH, THE UNTIGHT UPPER BOUND. $f \in o(g)$ if
$\forall c > 0 \land \exists n_0 : \forall n \geq n_0, f(n) < c \cdot g(n)$. That would mean $o(g) = \{f : \forall c > 0 \land \exists n_0 > 0, 0 \leq f < c \cdot g\quad \forall n \geq n_0\}$.

DEFINITION: LITTLE-OMEGA, THE UNTIGHT LOWER BOUND. $f \in \omega(g)$ if
$\forall c > 0 \land \exists n_0 : \forall n \geq n_0, f(n) > c \cdot g(n)$. That would mean $\omega(g) = \{f : \forall c > 0 \land \exists n_0 > 0, 0 \leq c \cdot g < f \quad \forall n \geq n_0\}$.

Earlier, we spoke of efficiency being in polynomial time. Surely, the student must be aware of constant time. We dedicate now a portion of the notes to some of the common functions observed in this class. Exponential time is characterised by $O(c^n)$ for $c > 1$. Polylogarithmic, "Polylog", time is characterisd by $O(\log^cn)$ for $c>0$ where $\log^cn = (\log n)^x$; it means polynomial in the $ log$ of $n$. Hence, $O(polylog(n))$ is the same as $O((\log n)^k)$ for some $k$.

FUNCTIONS

Having functions in mind can never hurt. Learn about their occurence and identities.

RECURRENCES

It is not always clear the complexity of an algorithm. Learn how forming recurrences can part the fog.

DIVIDE-AND-CONQUER

Break problems into smaller subproblems, solve them recursively, and combine the results with a simple merge step.

DYNAMIC PROGRAMMING

Record overlapping subproblems once, then reuse the stored results instead of recomputing them.

GREEDY METHODS

Choose locally optimal steps only when the exchange argument or cut property makes the choice safe.

MATROIDS

See a beautiful combinatorial theory perfectly describes many situations where the greedy method does yield optimal solutions.

GRAPHS

Learn about traversals, shortest-paths, and spanning-tree techniques, but keep them separate so the structure of the problem stays visible.

NETWORK FLOWS

Model problems as a graph having a flow coursing through it.

NP-COMPLETENESS

Use reductions to compare problem difficulty and keep the boundary between tractable and intractable problems clear.

RANDOMISED ALGORITHMS

Describe expected performance, probability of failure, and the role randomness plays in simplifying the analysis.

pwd: /~wtd/TEACHING/grad_algos_notes.html