Average Case Analysis of Algorithms on Sequences

This is a book on a topic that has witnessed a surge of interest over the last decade, owing in part to several novel applications, most notably in data compression and computational molecular biology. It describes methods employed in average case analysis of algorithms, combining both analytical and probabilistic tools.

Tools are illustrated through problems on words with applications to molecular biology, data compression, security, and pattern matching.

This book includes chapters on algorithms and data structures on words, probabilistic and analytical models, inclusion-exclusion principles, first and second moment methods, subadditive ergodic theorem and large deviations, elements of information theory, generating functions, complex asymptotic methods, Mellin transform and its applications, and analytic poissonization and depoissonization.

Review: Amazon.com

"Overall, this is a very good graduate-level textbook and a valuable (and almost self-contained) source of information for everyone interested in the analysis of algorithms."

Author : Wojciech Szpankowski, Department of Computer Sciences, Purdue University
ISBN : 047124063X
Pages : 576
Publisher : Wiley-Interscience
Publication Date : April 16, 2001

View/Download Average Case Analysis of Algorithms on Sequences

read more

Art Gallery Theorems and Algorithms

Art gallery theorems and algorithms are so called because they relate to problems involving the visibility of geometrical shapes and their internal surfaces. This book explores generalizations and specializations in these areas. Among the presentations are recently discovered theorems on orthogonal polygons, polygons with holes, exterior visibility, visibility graphs, and visibility in three dimensions. The author formulates many open problems and offers several conjectures, providing arguments which may be followed by anyone familiar with basic graph theory and algorithms. This work may be applied to robotics and artificial intelligence as well as other fields, and will be especially useful to computer scientists working with computational and combinatorial geometry.

This book is a research monograph on a topic that falls under both combinatorial geometry, a branch of mathematics, and computational geometry, a branch of computer science. The research described is recent: the earliest dates from the mid 1970s, and the majority is from the 1980s. Many of the results discussed have not yet been published. Advances continue to be made, especially on the algorithms side of the topic, and I have suffered the frustration of seeing each draft grow out of date before it was completed. Although the area of art gallery theorems has not stabilized, I believe the time is ripe for a survey, for two reasons.

First, the material is fascinating and accessible, and should be made available to a wider audience. Although this monograph is not a traditional textbook (there are no exercises, for example), I have used some of the material to great effect in a graduate/undergraduate course on computational geometry. The only prerequisites for understanding the material are basic graph theory, data structures, and algorithms. Thus it is easily accessible to upper-level undergraduates, or indeed to the "amateur." I have found that students can become very excited at finding themselves so quickly at the frontier of knowledge, with a chance of extending the frontier themselves (and several of mine have).

Second, I hope that this monograph will accelerate the maturing of the field by drawing attention to the many open problems. These consist of two types: finding more succinct proofs of the theorems, and proving or disproving the conjectures. There is a history in this field of proofs being drastically shortened after a few years, and I expect some of the more ungainly proofs in this book also will be similarly upstaged. The conjectures are certainly not all equally difficult. Some may be open only because no one has tried hard enough to settle them (edge guards?), some are open because they appear to be genuinely difficult (polygons with holes?), and some seem to await the new idea that will solve them in a single stroke (prison yard problem?). I will be disappointed if many of the unsolved problems posed in this book are not solved in the next decade.

Author : Joseph O'Rourke
ISBN : 0195039653
Pages : 304
Publisher : Oxford University Press
Publication Date : 1987

View/Download Art Gallery Theorems and Algorithms

read more

Art of Programming Contest

Art of Programming Contest


This book is designed to serve as a textbook for an algorithm course focusing on programming as well as a programming course focusing on algorithms. The book is specially designed to train students to participate in competitions, especially the ACM International Collegiate Programming Contest.

The book covers several important topics related to the development of programming skills such as, fundamental concepts of contest, game plan for a contest, essential data structures for contest, input/output techniques, brute force method, mathematics, sorting, searching, greedy algorithms, dynamic programming, graphs, computational geometry, Valladolid Online Judge problem category, selected ACM programming problems, common codes/routines for programming, Standard Template Library (STL), PC2 contest administration and team guide. The book also lists some important websites/books for ACM/ICPC Programmers.

About ACM International Collegiate Programming Contest:

The Association for Computing Machinery (ACM) sponsors a yearly programming contest, recently with the sponsorship of IBM. The contest is both well-known and highly regarded: in 2005, 2400 teams competed from more than 100 nations competed at the regional levels. Sixty of these went on to the international finals. This contest is known as ACM International Collegiate Programming Contest (ICPC).

The regional contest itself is typically held in November, with the finals in March. Teams of three students use C, C++, or Java to solve six to eight problems within five hours. One machine is provided to each team, leaving one or two team members free to work out an approach. Often, deciding which problems to attack first is the most important skill in the contest. The problems test the identification of underlying algorithms as much as programming savvy and speed.

Review(s):
Dr. M. Lutfar Rahman, Professor, Department of Computer Science and Engineering, University of Dhaka:

"I believe that the book will be book will be of immense use for young programmers interested in taking part in programming competitions."

Author : Ahmed Shamsul Arefin, Member, ACM Valladolid Online Judge Algorithmic Team
Foreworded By : Professor Miguel A. Revilla, ACM-ICPC International Steering Committee Member and Problem Archivist
ISBN : 984-32-3382-4
Pages : 247
Publication Date : 2006
Publisher : Gyankosh Prokashoni

View/Download Art of Programming Contest | Valladolid Online Judge Problem Set Archive

read more

Algorithms in the Real World: Lecture Notes

This document contains the lecture notes taken by the students in the course Algorithms in the Real World taught at UC Berkeley during the Fall semester, 1997. The class covered the following set of ten topics: Compression, Cryptography, Linear Programming, Integer Programming, Triangulation, N-body simulation, VLSI Physical Design, Pattern Matching in Biology, Indexing, and Clustering. Between 2 and 3 lectures were dedicated to each topic. For all topics this document looked both at algorithms and at case studies in which the problems are used in real-world applications.

The class was a graduate class and assumed that the students came in with a working knowledge of the material covered in a standard algorithms textbook, such as Cormen, Leiserson and Rivest's Introduction to Algorithms. A goal of the class was to have the students gain an appreciation of how interesting algorithms and data-structures are used in many real-world applications.

The notes contained in this document are based on what was covered in the lectures and are not meant to be complete, and although the scribe takers corrected many of the mistakes in the lectures, many others got through. Unfortunately the notes contain very few references to the original work on which they rely. Instead, included at the end of the document is a list of primary texts on the topics from which one can find further information.

Author : Guy Blelloch, Department of Computer Science, Carnegie Mellon University
Publication Date : April 1998

View/Download Algorithms in the Real World: Lecture Notes | Course 15-853 Page

read more

Data Structures and Algorithms with Object-Oriented Design Patterns in C#

The primary goal of this book is to promote object-oriented design using C# and to illustrate the use of the emerging object-oriented design patterns. Experienced object-oriented programmers find that certain ways of doing things work best and that these ways occur over and over again. The book shows how these patterns are used to create good software designs. In particular, the following design patterns are used throughout the text: singleton, container, enumeration, adapter and visitor.

Virtually all of the data structures are presented in the context of a single, unified, polymorphic class hierarchy. This framework clearly shows the relationships between data structures and it illustrates how polymorphism and inheritance can be used effectively. In addition, algorithmic abstraction is used extensively when presenting classes of algorithms. By using algorithmic abstraction, it is possible to describe a generic algorithm without having to worry about the details of a particular concrete realization of that algorithm.

A secondary goal of the book is to present mathematical tools just in time. Analysis techniques and proofs are presented as needed and in the proper context. In the past when the topics in this book were taught at the graduate level, an author could rely on students having the needed background in mathematics. However, because the book is targeted for second and third-year students, it is necessary to fill in the background as needed. To the extent possible without compromising correctness, the presentation fosters intuitive understanding of the concepts rather than mathematical rigor.

This book presents the various data structures and algorithms as complete C# program fragments. All the program fragments presented in this book have been extracted automatically from the source code files of working and tested programs. It has been tested that by developing the proper abstractions, it is possible to present the concepts as fully functional programs without resorting to pseudo-code or to hand-waving.

This book does not teach the basics of programming. It is assumed that you have taken an introductory course in programming and that you have learned how to write a program in C#. That is, you have learned the rules of C# syntax and you have learned how to put together C# statements in order to solve rudimentary programming problems.

Author(s) : Bruno R. Preiss
Publication Date : 2001

View/Download Data Structures and Algorithms with Object-Oriented Design Patterns in C#

read more

Data Structures and Algorithms with Object-Oriented Design Patterns in C++

The primary goal of this book is to promote object-oriented design using C++ and to illustrate the use of the emerging object-oriented design patterns. Experienced object-oriented programmers find that certain ways of doing things work best and that these ways occur over and over again. The book shows how these patterns are used to create good software designs. In particular, the following design patterns are used throughout the text: singleton, container, iterator, adapter and visitor.

Virtually all of the data structures are presented in the context of a single, unified, polymorphic class hierarchy. This framework clearly shows the relationships between data structures and it illustrates how polymorphism and inheritance can be used effectively. In addition, algorithmic abstraction is used extensively when presenting classes of algorithms. By using algorithmic abstraction, it is possible to describe a generic algorithm without having to worry about the details of a particular concrete realization of that algorithm.

In the past when the topics in this book were taught at the graduate level, students could be expected of having the needed background in mathematics. However, because the book is targeted for second- and third-year students, it is necessary to fill in the background as needed.

Reviews: Amazon.com

"Who should buy this book? Students with a good grasp of basic calculus, who want a thoroughly academic treatment of algorithms in C++ in order to pass Computer Science."

Author(s) : Bruno R. Preiss
Publication date : Aug 1998
ISBN : 0-471-24134-2
Pages : 688
Publisher : John Wiley & Sons

View/Download Data Structures and Algorithms with Object-Oriented Design Patterns in C++

read more

Data Structures and Algorithms With Object-Oriented Design Patterns in Java

This book is about the fundamentals of data structures and algorithms -- the basic elements from which large and complex software artifacts are built. The target is to teach you to develop a solid understanding of a data structure, which requires three things.

First, you will learn how the information is arranged in the memory of the computer. Second, you will learn the algorithms for manipulating the information contained in the data structure. And third, you will learn the performance characteristics of the data structure so that when called upon to select a suitable data structure for a particular application, you will be able to make an appropriate decision.

This book also illustrates object-oriented design and it promotes the use of common, object-oriented design patterns. The algorithms and data structures in the book are presented in the Java programming language. Virtually all the data structures are presented in the context of a single class hierarchy. This commitment to a single design allows the programs presented in the later chapters to build upon the programs presented in the earlier chapters.

Reviews: Amazon.com

"I would actually say that this is a very readable introductory treatment on data structures."

LTSN-ICS Book Review

"Unfortunately the approach will appeal more to lecturers who understand the material and enjoy cerebral ideas than to students who are trying to get to grips with the material and like to be given practical information."

Author(s) : Bruno R. Preiss
Publication date : Aug 1999
ISBN : 0-471-34613-6
Publisher : John Wiley & Sons

View/Download Data Structures and Algorithms With Object-Oriented Design Patterns in Java

read more

Design and Analysis of Algorithms: Course Notes

This is a compilation of lecture notes, used by the author to teach CMSC 651: Design and Analysis of Algorithms at Dept. of Computer Science, University of Maryland. This course has been taught several times and each time the coverage of the topics differs slightly.

The notes will cover many different topics. Readers will start out by studying various combinatorial algorithms together with techniques for analyzing their performance. Readers will also study linear programming and understand the role that it plays in the design of combinatorial algorithms. Finally readers will go on to the study of NP-completeness and NP-hard problems, along with polynomial time approximation algorithms for these hard problems.

The material for the first few weeks was taken primarily from the textbook on Algorithms by Cormen, Leiserson and Rivest. In addition, the author have used material from several other books such as the Combinatorial Optimization book by Papadimitriou and Steiglitz, as well as the Network Flow book by Ahuja, Magnanti and Orlin and the edited book on Approximation Algorithms by Hochbaum. A few papers were also covered, containing some very important and useful techniques that should be in the toolbox of every algorithms researcher.

Author : Samir Khuller, Dept. of Computer Science, University of Maryland
Publication Date : August 2003

View / Download Design and Analysis of Algorithms: Course Notes

read more

Design and Analysis of Computer Algorithms

Programming is a very complex task, and there are a number of aspects of programming that make it so complex. The first is that most programming projects are very large, requiring the coordinated efforts of many people. (This is the topic a course like software engineering.) The next is that many programming projects involve storing and accessing large quantities of data efficiently. (This is the topic of courses on data structures and databases.) The last is that many programming projects involve solving complex computational problems, for which simplistic or naive solutions may not be efficient enough. The complex problems may involve numerical data (the subject of courses on numerical analysis), but often they involve discrete data. This is where the topic of algorithm design and analysis is important.

Although the algorithms discussed in this course will often represent only a tiny fraction of the code that is generated in a large software system, this small fraction may be very important for the success of the overall project. An unfortunately common approach to this problem is to first design an inefficient algorithm and data structure to solve the problem, and then take this poor design and attempt to fine-tune its performance. The problem is that if the underlying design is bad, then often no amount of fine-tuning is going to make a substantial difference.

The focus of this course is on how to design good algorithms, and how to analyze their efficiency. This is among the most basic aspects of good programming.

Course Overview:

This course will consist of a number of major sections. The first will be a short review of some preliminary material, including asymptotics, summations, and recurrences and sorting. These have been covered in earlier courses, and so we will breeze through them pretty quickly. We will then discuss approaches to designing optimization algorithms, including dynamic programming and greedy algorithms. The next major focus will be on graph algorithms. This will include a review of breadth-first and depth-first search and their application in various problems related to connectivity in graphs. Next we will discuss minimum spanning trees, shortest paths, and network flows. We will briefly discuss algorithmic problems arising from geometric settings, that is, computational geometry.

Most of the emphasis of the first portion of the course will be on problems that can be solved efficiently, in the latter portion we will discuss intractability and NP-hard problems. These are problems for which no efficient solution is known. Finally, we will discuss methods to approximate NP-hard problems, and how to prove how close these approximations are to the optimal solutions.

Author : David M. Mount, Department of Computer Science, University of Maryland
Publication Date : 2003

View/Download Design and Analysis of Computer Algorithms | Course Website

read more

Efficient Algorithms for Sorting and Synchronization

This is a thesis submitted by the author for the degree of Doctor of Philosophy at The Australian National University. This thesis presents efficient algorithms for internal and external parallel sorting and remote data update. The sorting algorithms approach the problem by concentrating first on highly efficient but incorrect algorithms followed by a cleanup phase that completes the sort.

The remote data update algorithm, rsync, operates by exchanging block signature information followed by a simple hash search algorithm for block matching at arbitrary byte boundaries. The last chapter of the thesis examines a number of related algorithms for text compression, differencing and incremental backup.

Contents:
1. Internal Parallel Sorting
2. External Parallel Sorting
3. The rsync algorithm
4. rsync enhancements and optimizations
5. Further applications for rsync
6. Conclusion

Author(s) : Andrew Tridgell
Pages : 115
Publication Date : Feb 1999

View/Download Efficient Algorithms for Sorting and Synchronization

read more

Foundations of Computer Science

These are the lecture notes for the Foundations of Computer Science course at the Computer Laboratory, University of Cambridge.

The principal aim of this course is to present the basic principles of programming. As the introductory course of the Computer Science, it caters to students from all backgrounds. To those who have had no programming experience, it will be comprehensible; to those experienced in languages such as C, it will attempt to correct any bad habits that they have learnt.

A further aim is to introduce the principles of data structures and algorithms. The course will emphasise the algorithmic side of programming, focusing on problem-solving rather than on hardware-level bits and bytes. Accordingly it will present basic algorithms for sorting, searching, etc., and discuss their efficiency using O-notation. Worked examples (such as polynomial arithmetic) will demonstrate how algorithmic ideas can be used to build efficient applications.

The course will use a functional language (ML). ML is particularly appropriate for inexperienced programmers, since a faulty program cannot crash. The course will present the elements of functional programming, such as curried and higher-order functions. But it will also discuss traditional (procedural) programming, such as assignments, arrays, pointers and mutable data structures.

Author : Lawrence C Paulson, Computer Laboratory, University of Cambridge
Publication Date : 2000

View/Download Foundations of Computer Science

read more

GNU libavl Online Book

GNU libavl is a library in ANSI C for manipulation of various types of binary trees. This book provides an introduction to binary tree techniques and presents all of libavl's source code, along with annotations and exercises for the reader. It also includes practical information on how to use libavl in your programs and discussion of the larger issues of how to choose efficient data structures and libraries. The book concludes with suggestions for further reading, answers to all the exercises, glossary, and index.

Intended Audience:

This book is intended both for novices interested in finding out about binary search trees and practicing programmers looking for a cookbook of algorithms. It has several features that will be appreciated by both groups:

# Tested code: With the exception of code presented as counterexamples, which are clearly marked, all code presented has been tested. Most code comes with a working program for testing or demonstrating it.
# No pseudo-code: Pseudo-code can be confusing, so it is not used.
# Motivation: An important goal is to demonstrate general methods for programming, not just the particular algorithms being examined. As a result, the rationale for design choices is explained carefully.
# Exercises and answers: To clarify issues raised within the text, many sections conclude with exercises. All exercises come with complete answers in an appendix at the back of the book.

Experienced programmers should find the exercises particularly interesting, because many of them present alternatives to choices made in the main text.

Author : Ben Pfaff, Computer Science Ph.D. student, Stanford University
Publication Date : 2006
Free License : GNU General Public License

View/Download GNU libavil Online Book

read more

Practical Optimization: A Gentle Introduction

This book is designed as a one-term introduction to the most important topics in applied optimization. It is impossible to cover all of optimization in a one-term course: there are entire yearlong courses on each of the individual topics that we will cover! This book provides a fairly broad survey at a medium depth. There are numerous topics that you should be aware of, but which cannot be covered in an introductory book like this one: brief sketches of these topics appear throughout the book.

The main goals of a course using this book should be to equip students to:

1. recognize problems that can be tackled using the tools of applied optimization,
2. formulate optimization problems correctly and appropriately,
3. solve optimization problems, primarily by selecting and applying the correct solvers, but also possibly by writing special software or hiring experts.

These abilities will be an excellent addition to your skills toolkit, and especially useful as the world becomes more complex and computer-centric. Note that a course in optimization or operations research is required in most MBA courses, in business, industrial engineering (and many other engineering programs), and economics. Such courses are usually a recommended option in computer science as well. These courses are included in all those programs precisely because the material finds so many practical applications.

Author : John W. Chinneck, Systems and Computer Engineering, Carleton University
Publication Date : November 2007

View/Download Practical Optimization: A Gentle Introduction

read more

Optimization Algorithms on Matrix Manifolds

Optimization Algorithms on Matrix Manifolds offers techniques with broad applications in linear algebra, signal processing, data mining, computer vision, and statistical analysis. It can serve as a graduate-level textbook and will be of interest to applied mathematicians, engineers, and computer scientists.

Many problems in the sciences and engineering can be rephrased as optimization problems on matrix search spaces endowed with a so-called manifold structure. This book shows how to exploit the special structure of such problems to develop efficient numerical algorithms. It places careful emphasis on both the numerical formulation of the algorithm and its differential geometric abstraction--illustrating how good algorithms draw equally from the insights of differential geometry, optimization, and numerical analysis. Two more theoretical chapters provide readers with the background in differential geometry necessary to algorithmic development. In the other chapters, several well-known optimization methods such as steepest descent and conjugate gradients are generalized to abstract manifolds. The book provides a generic development of each of these methods, building upon the material of the geometric chapters. It then guides readers through the calculations that turn these geometrically formulated methods into concrete numerical algorithms. The state-of-the-art algorithms given as examples are competitive with the best existing algorithms for a selection of eigenspace problems in numerical linear algebra.

Authors : P.A. Absil, R. Mahony & R. Sepulchre
ISBN : 0691132984
Pages : 240
Publisher : Princeton University Press
Publication Date : December 2007

View/Download Optimization Algorithms on Matrix Manifolds

read more

Object-oriented Programming with Ansi-C

Object-oriented programming is the current cure-all — although it has been around for much more then ten years. At the core, there is little more to it then finally applying the good programming principles which we have been taught for more then twenty years. C++ (Eiffel, Oberon-2, Smalltalk ... take your pick) is the New Language (ed: this book was published in 1993) because it is object-oriented — although you need not use it that way if you do not want to (or know how to), and it turns out that you can do just as well with plain ANSI-C. Only object-orientation permits code reuse between projects — although the idea of subroutines is as old as computers and good programmers always carried their toolkits and libraries with them.

This book is not going to praise object-oriented programming or condemn the Old Way. We are simply going to use ANSI-C to discover how object-oriented programming is done, what its techniques are, why they help us solve bigger problems, and how we harness generality and program to catch mistakes earlier. Along the way we encounter all the jargon — classes, inheritance, instances, linkage, methods, objects, polymorphisms, and more — but we take it out of the realm of magic and see how it translates into the things we have known and done all along.

Intended Audience:

I had fun discovering that ANSI-C is a full-scale object-oriented language. To share this fun you need to be reasonably fluent in ANSI-C to begin with — feeling comfortable with structures, pointers, prototypes, and function pointers is a must. Working through the book you will encounter all the newspeak — according to Orwell and Webster a language "designed to diminish the range of thought" — and I will try to demonstrate how it merely combines all the good programming principles that you always wanted to employ into a coherent approach. As a result, you may well become a more proficient ANSI-C programmer.



Author : Axel-Tobias Schreiner, Computer Science Department, Rochester Institute of Technology
Publication Date : October 1993

View/Download Object-oriented Programming with Ansi-C

read more

Notes for the Course of Data Structures

The study of data structures and the algorithms that manipulate them is among the most fundamental topics in computer science. Most of what computer systems spend their time doing is storing, accessing, and manipulating data in one form or another. Some examples from computer science include networking, information retrieval, compilers and computer graphics.

This course will deal with the first two tasks of storage and access at a very general level. (The last issue of manipulation is further subdivided into two areas, manipulation of numeric or floating point data, which is the subject of numerical analysis, and the manipulation of discrete data, which is the subject of discrete algorithm design.) A good understanding of data structures is fundamental to all of these areas.

Whenever we deal with the representation of real world objects in a computer program we must first consider a number of issues: modeling, operations, representation and algorithms. Note that the first two items are essentially mathematical in nature, and deal with the "what" of a data structure, whereas the last two items involve the implementation issues and the "how" of the data structure. The first two essentially encapsulate the essence of an abstract data type (or ADT). In contrast the second two items, the concrete issues of implementation, will be the focus of this course.

This course will explore a number of different data structures, study their implementations, and analyze their efficiency (both in time and space). One of the goals will be to provide the students with the tools that they will need to design and implement their own data structures to solve their own specific problems in data storage and retrieval.

Course Overview:

This course will consider many different abstract data types, and many different data structures for storing each type. Note that there will generally be many possible data structures for each abstract type, and there will not generally be a "best" one for all circumstances. It will be important for the student as a designer of data structures to understand each structure well enough to know the circumstances where one data structure is to be preferred over another.

Author : Dave Mount, Department of Computer Science, University of Maryland
Publication Date : 2001

View/Download Notes for the Course of Data Structures | Course web page

read more

Notes for the Course of Algorithms

What is algorithm design? An algorithm was defined to be any well-defined computational procedure that takes some values as input and produces some values as output. Like a cooking recipe, an algorithm provides a step-by-step method for solving a computational problem.

A good understanding of algorithms is essential for a good understanding of the most basic element of computer science: programming. Unlike a program, an algorithm is a mathematical entity, which is independent of a specific programming language, machine, or compiler. Thus, in some sense, algorithm design is all about the mathematical theory behind the design of good programs.

One of the elements that this course focuses on is to try to study algorithms as pure mathematical objects, and so ignore issues such as programming language, machine, and operating system. This has the advantage of clearing away the messy details that affect implementation. But these details may be very important.

Document Organization:

The notes will consist of three major sections. The first is on the mathematical tools necessary for the analysis of algorithms. This will focus on asymptotics, summations, recurrences. The second element will deal with one particularly important algorithmic problem: sorting a list of numbers. The notes will show a number of different strategies for sorting, and use this problem as a case study in different techniques for designing and analyzing algorithms. The final third of the course will deal with a collection of various algorithmic problems and solution techniques. Finally the notes will close with a very brief introduction to the theory of NP-completeness. NP-complete problem are those for which no efficient algorithms are known, but no one knows for sure whether efficient solutions might exist.

Author : Dave Mount, Department of Computer Science, University of Maryland
Publication Date : 1998

View/Download Notes for the Course of Algorithms | Course web page

read more

Notes for the Course of Advanced Algorithms

The aim of the course "Advanced Algorithms" is at least twofold. One aim is to describe a couple of the classical algorithms which are not taught in a first algorithms course. The second is to give a general understanding of efficient algorithms and to give the student a better understanding for how to design and analyze efficient algorithms. The overall approach of the course is theoretical, we work with pencil and paper. The main emphasis of the course is to get an algorithm with a good asymptotic running time. In most cases this coincides with efficient in practice and the most notable example where this is not true is matrix multiplication where the implied constants are too large to make the algorithms be of practical value.

Although the lectures are theoretical, students are asked to implement some basic algorithms in the homework sets. Our hope is that this gives at least some balance between practice and theory.

The current set of lecture notes include all topics covered in the course in its past four appearances in spring 1995, spring 1997, fall 1997, and fall 1998. The course in 1995 was mostly taken by graduate student while the later courses were mostly taken by undergraduate students. Thus some of the more advanced topics, like matrix multiplication, lattice basis reduction and provable polynomial time for integer polynomial factorization, was only covered in 1995 and may not be covered in coming years. However, for the interested reader we have kept those sections in these notes. Also when it comes to the rest of the material we do not expect to cover all algorithms each time the course is given. The choice of which algorithms to cover is done at the beginning of a course to make it possible for the participants to influence this decision. The choice is not limited to the algorithms included in these notes and I would be happy to include any desired new topic that would be on a topic agreeing with the course philosophy.

Notes for the Course of Advanced Algorithms
Author : Johan Håstad, School of Computer Science and Communication, Kungliga Tekniska högskolan
Publication Date : January 2000

View/Download Notes for the Course of Advanced Algorithms (gzipped) | PostScript | PDF

read more

Jeff Erickson's Algorithms Course Materials

This class is ultimately about learning two skills that are crucial for computer scientists: how to think about algorithms and how to talk about algorithms. Along the way, you'll pick up a bunch of algorithmic facts—mergesort runs in O(n log n) time; the amortized time to search in a splay tree is O(log n); greedy algorithms usually don't produce optimal solutions; the traveling salesman problem is NP-hard—but these aren't the point of the course. You can always look up mere facts in a textbook or on the web, provided you have enough intuition and experience to know what to look for. That's why we let you bring cheat sheets to the exams; we don't want you wasting your study time trying to memorize all the facts you've seen. You'll also practice a lot of algorithm design and analysis skills—finding useful (counter)examples, developing induction proofs, solving recurrences, using big-Oh notation, using probability, giving problems crisp mathematical descriptions, and so on. These skills are very useful, but they aren't really the point of the course either. At this point in your educational career, you should be able to pick up those skills on your own, once you know what you're trying to do.

The first main goal of this course is to help you develop algorithmic intuition. How do various algorithms really work? When you see a problem for the first time, how should you attack it? How do you tell which techniques will work at all, and which ones will work best? How do you judge whether one algorithm is better than another? How do you tell whether you have the best possible solution?

Our second main goal is to help you develop algorithmic language. It's not enough just to understand how to solve a problem; you also have to be able to explain your solution to somebody else. I don't mean just how to turn your algorithms into working code—despite what many students (and inexperienced programmers) think, 'somebody else' is not just a computer. Nobody programs alone. Code is read far more often than it is written, or even compiled. Perhaps more importantly in the short term, explaining something to somebody else is one of the best ways of clarifying your own understanding. As Richard Feynman apocryphally put it, "If you can't explain what you're doing to your grandmother, you don't understand it."

Unfortunately, there is no systematic procedure—no algorithm—to determine which algorithmic techniques are most effective at solving a given problem, or finding good ways to explain, analyze, optimize, or implement a given algorithm. Like many other human activities (music, writing, juggling, acting, martial arts, sports, cooking, programming, teaching, etc.), experts will disagree on the relative values of different techniques. Ultimately, the only way to master these skills is to make them your own, through practice, practice, and more practice. We can't teach you how to do well in this class. All we can do is lay out a few tools, show you how to use them, create opportunities for you to practice, and give you feedback based on our own experience and intuition. The rest is up to you.

Jeff Erickson's Algorithms Course Materials
Author : Jeff Erickson, Associate Professor of Computer Science, University of Illinois at Urbana-Champaign
Publication Date : January 2007
Free License : Creative Commons Attribution-NonCommercial-ShareAlike 2.5 License

View/Download Jeff Erickson's Algorithms Course Materials

read more

Introduction to Algorithms

The study of algorithms - carefully-crafted solutions to particularly important programming problems - is one of the oldest areas in Computer Science. In order truly to understand an algorithm we have first to understand why it works at all, then to understand how it performs in general - how long it takes and how much space it takes tip while it is working - and last, understand how to tweak the algorithm to make its performance fit the particular circumstances in which we want to use it. In the case of some of the famous algorithms we shall meet, like quicksort, we also have to understand why it isn't easy to do better.

So the course will focus on two issues: correctness - how we say what an algorithm is supposed to do, and how we can argue that it actually does it -and so-called complexity - how to estimate the amount of work an algorithm must do to perform its task in general, or on average, or in the worst case. There will be some experimental work, trying to verify in practice the theoretical measures that can be developed by using mathematical arguments, but much of the course will be about analysing algorithms with pencil and paper.

Some of the algorithms we shall analyse are intensely beautiful. To appreciate their beauty we have to realise how much better they are than the first naive attempts one of us might make to solve the same problem, and how concisely they solve the problem which they are designed to solve. All of the algorithms we shall analyse are useful. Some of them are not entirely understood - it is a recurring feature of Computer Science that we continually invent things which we only partly understand.


Introduction to Algorithms
Author : Paul Taylor, School of Computer Science, The University of Manchester
Publication Date : 2001

View/Download Introduction to Algorithms | Website

read more