Algorithms -Professor Shai Simonson

ArsDigita University

Month 5: Algorithms -Professor Shai Simonson

Syllabus

General information about our text and readings:

Our text is Introduction to Algorithms by Cormen, Leiserson and Rivest. It is an encyclopedic

work that serves well not only as an introduction to algorithms, but also as a reference for discrete

mathematics, data structures and simple computational complexity. Chapters 2-6, and 11-12 are topics

that you have seen before in month 1 (Scheme), month 2 (Discrete Math) or month 4 (J ava –Software

Engineering). I will not assign these as readings, but you are expected to be familiar with these topics

and use the sections for reference when necessary. We will use recitations for reviewing these topics as

necessary.

There are many sections in the text that we will not cover in class. In particular, I believe that

the material on parallel algorithms (chapters 28 -30) is best left for a graduate level course that

concentrates exclusively on that topic. The material on advanced data s tructures like binomial heaps and

Fibonacci heaps represents amortized improvements over simple binary heaps and are heavily dependent

on concepts from the discrete math course. This is also true for the more advanced graph algorithms of

max-flow/min-cut and matching problems. We will leave the study of these topics (Chapters 20 -21, 27)

for your own personal future projects. B -trees (Chapter 19) are a fundamental data structure used at the

disk storage level behind relational databases, and is left as a topic in the database course. All these

more advanced topics represent too deep of an excursion for a first course that needs to cover so much

breadth.

Behind every algorithm are theorems and proofs, mostly proofs by induction. Behind every

analysis of an algorithm is a sum, a recurrence equation, or a combinatorial argument. Throughout the

course we will try to separate the discrete math details from the algorithms concentrating on the latter in

class, and leaving the former for reading and reference. You may not remember all the mathematical

details from the discrete math course, but as long as you remember the basics then the proofs and

calculations will be accessible.

Of the many applications in which algorithms arise, we will study graph algorithm s and

geometric algorithms, leaving out mathematical algorithms and string matching unless time allows. You

have seen a lot of the mathematical algorithms (Chapters 31, 33) in month 2 (Discrete Math), and the

Fast Fourier Transform (Chapter 32), which yo u have not yet studied, is too advanced for a first course.

The string matching algorithms (Chapter 34), although interesting and practical, are a special topic

lacking the general scope of graph and geometric algorithms.

A detailed syllabus with readings follows below:

Week 1:Introduction and Overview.

Methods of algorithm design and analysis. The relationship of algorithms to data structures.

Categorizing algorithms by methodology. Categorizing algorithms by application. Coping with

intractability. Sorting and Searching. Hashing and basic data structures (recitation). Discrete

Math Review (recitation).

Reading:CLR –Chapters 1, 7, 8, 9, 10, 13.0 –13.3, 14, 36.0 –36.1, 37.0, handouts.

Lecture 1:The big picture. Algorithm methodologies –divide and conquer, dynamic

programming, greedy strategy. Algorithm analysis –worst case, average case, amortized.

Algorithm applications –sorting and searching, graphs, mathematical –(number theory,

algebra and linear algebra), string matchi ng, geometrical. Coping with

...