# Algorithms

Lecture: Devorah Kletenik

1 Rationale

Analysis of algorithms involves characterizing the amount of resources con-

sumed by an algorithm, measured as a function of input length, and typ-

ically bounded in the worst case. The most common resources considered

are running time and space used, but others may be considered as well, such

as number of random bits used or number of blocks read from secondary

storage. In algorithm design, we seek algorithms that have good worst-case

resource requirements and other attractive qualities, such as optimality or

approximation guarantees, good performance \in practice", parallelizability,

and simplicity.

2 Course Description

This course covers the design and analysis of algorithms for a number of

fundamental problems, such as sorting, order statistics, minimum spanning

trees, shortest paths, matching, maximum ow, minimum cut, satisability,

knapsack, set covering, and linear programming. Common algorithm design

techniques will be emphasized, including greedy, divide-and-conquer, and dy-

namic programming, as well as formulating problems as linear programs and

the use of randomness. Some ecient data structures will also be examined,

primarily hash tables, but also heaps and binary search trees. Finally, we

will briey discuss the halting problem, NP-completeness, and reductions.

Implementation projects might be assigned, applying algorithms to real-

world applications.

3 Topic List

Growth of Functions

•  Asymptotic Notation
•  Recurrence Equation

Divide-and-Conquer:

•  Sorting
•  Heapsort
•  Median and other Order Statistics

Greedy Algorithms:

•  Activity Selection
•  Minimum Spanning Tree: Prim, Kruskal, Borvka
•  Matroids
•  Knapsack
•  Set Covering

Randomized Algorithms:

•  Quicksort
•  Satisability

Iterative Algorithms:

•  Page Rank
•  K-means
•  Steepest Descent

Dynamic Programming:

•  Longest Common Subsequence
•  Knapsack
•  Independent Set
•  Dijkstra Algorithm for Shortest Paths

Data Structures:

•  Heaps
•  Binary Search Trees
•  Hash Tables
•  Disjoint Sets

Network Flows:

• Ford-Fulkerson
• Bipartite Matching
• Maximum Flow and Minimum Cut

Linear Programming (and Integer Programming):

•  Standard and Other Forms
•  Simplex
•  Duality

Computability and Complexity:

• Halting Problem
• Polynomial Time
• Complexity Classes P and NP
• NP-Completeness
• Reductions

4 Learning Goals

The student should be able to:

--Explain and analyze the performance guarantees (in terms of optimality

and eciency) of standard algorithms for sorting, minimum spanning

trees, shortest paths, maximum ow, hashing, and knapsack.

--Understand and program divide-and-conquer algorithms and the use of

search trees.

--Understand the principles of greedy algorithms and matroids.

Know the mathematical denitions needed for the specication of min-

imum spanning trees and be able to analyze and program algorithms

for nding such trees.

--Seek solutions to newly encountered problems by applying basic algo-

rithm design techniques, such as divide-and-conquer, greedy, dynamic

programming; and judge which approaches are most appropriate or

promising for the problem at hand.

Formulate problems as (possibly integer) linear programs.

Investigate or make informed judgments about whether a given problem

is likely to be NP-complete.

5 Assessment

The course grade will be determined by:

• Homework (and, possibly, in-class) problems (which may include programming): 65
• Final exam: 35

6 Textbook

Introduction to Algorithms, (latest edition); Cormen, Leiserson, Rivest, and

Stein; MIT Press.

7 Reference Text

Algorithm Design (latest edition); Kleinberg and Tardos; Pearson.