Adaptive Object-Oriented Software: The Demeter Method with Propagation Patterns

This book presents a complete methodology for adaptive programming in any object-oriented language. Lieberherr's method provides a new approach to object-oriented program design that goes beyond object encapsulation and hard-coded navigation paths to achieve more flexible interactions among objects. Designers using this adaptive method work at a higher, more schematic level of abstraction to design software programs. Graph notation is used to represent the class structure of the program, and a "propagation pattern" language describes how to distribute meaningful methods (including navigation) across the program's structure. Using this method, software designers can create programs that are easily modified and adaptable as needs evolve.

Reviews: Amazon.com

"Unfortunately, apart from highlighting the problems of OO successfully, he singularly failed to convince me of the adaptive OO approach."

Author(s) : Karl J. Lieberherr
Publication date : August 1995
ISBN : 0-534-94602-X
Pages : 616
Publisher : PWS Publishing Co.

View/Download Adaptive Object-Oriented Software

read more

Building Skills in Object-Oriented Design - Step-by-Step Construction of A Complete Application

Some software developers find themselves stalled when trying to do object-oriented (OO) design. As programmers, they've understood the syntax of a programming language, and pieced together small examples. However, it is often difficult to take the next step to becoming a designer. Because this transition from guided learning of language features to self-directed design work is often ignored, programmers are left to struggle through their first design projects without appropriate skills or support. While it is critically important to examine examples of good design, a finished product doesn't reveal the author's decision-making process that created the design.

The most notable consequence of this skills gap is the creation of software that is far more complex than necessary to effectively solve a given problem. This, in turn, leads to software with high maintenance costs stemming from the low quality. It also leads to an unfair indictment of OO technology; this is usually voiced as “we tried OO programming and it failed.”

The intent of this book is to help the beginning designer by giving them a sequence of interesting and moderately complex exercises in OO design. This book can also help managers develop a level of comfort with the process of OO software development. The applications we will build are a step above trivial, and will require some careful thought and design. Further, because the applications are largely recreational in nature, they are interesting and engaging. This book allows the reader to explore the processes and artifacts of OO design before project deadlines make good design seem impossible.

Author : Steven F. Lott
Publication Date : 2005
Free License : Creative Commons License Attribution-Noncommercial-No Derivative Works 2.0 Generic

View/Download Building Skills in Object-Oriented Design | Single HTML | PDF

read more

Introduction to Object-Oriented Programming Using C++

This is a collection of lectures in the on-line course Introduction to Object-Oriented Programming Using C++. In this course, object-orientation is introduced as a new programming concept which should help you in developing high quality software. Object-orientation is also introduced as a concept which makes developing of projects easier.

However, this is not a course for learning the C++ programming language. If you are interested in learning the language itself, you might want to go through other tutorials, such as C++: Annotations by Frank Brokken and Karel Kubat. In this tutorial only those language concepts that are needed to present coding examples are introduced.

Author(s) : Peter Müller
Publication date : Aug 1997

View/Download Introduction to Object-Oriented Programming Using C++

read more

Java Au Naturel - Guide to Object Oriented Design, 4th Edition

This book focuses on software development with an object-oriented approach. Java is used for the implementation, since it's well suited for learning and doing object-oriented software development.

Programmer only learns by doing. In this book, readers will work with many different situations where software development is necessary. Readers should not start by learning Java's eight different primitive types or its five different control statements. They should start by seeing how to develop software for a particular realistic situation. And they should learn the language features they need for the situation as the need arises.

This book starts by introducing the objects that make drawings. In this context readers will learn to send messages to objects to carry out simple tasks. More importantly, this book shows readers how to "teach" those objects to put together a sequence of simple actions to perform a complex task. These "better-trained" objects have new capabilities in addition to the ones they inherit from the original specifications. This inheritance technique eventually makes the job much easier. Bigger jobs can be completed with less work and less chance of getting it wrong if there are new objects that take over most of the work. When objects are used this way, they should be thought of as the agents or executive assistants.

Intended Audience:

This book does not require any knowledge of programming or any mathematics beyond elementary algebra and (in a few places) a bit of trigonometry.

Author : Dr. William C. Jones, Jr., Department of Computer Science, Central Connecticut State University
Publication Date : May 26, 2004

View/Download Java Au Naturel - Guide to Object Oriented Design, 4th Edition

read more

Java: An Object First Approach

Java: An Object First Approach provides a thorough introduction to the production of software artefacts, a process known as software development, using the programming language Java. The book is intended for use with readers/students starting their software development education and can also be used at a more advanced level as an Object-Oriented book.

The author uses a spiral approach to present object-oriented concepts and techniques. The development of a class hierarchy is utilized, stressing a design, build, test cycle. An extensive case study at the conclusion of the book pulls the concepts together.

Author(s) : Fintan Culwin
Publication date : Oct 1997
ISBN : 0-138-58457-5
Pages : 393
Publisher : Prentice Hall

View/Download Java: An Object First Approach

read more

Object-Oriented Programming And The Objective-C Language

Object-oriented programming, like most interesting new developments, builds on some old ideas, extends them, and puts them together in novel ways. The result is many-faceted and a clear step forward for the art of programming. An object- oriented approach makes programs more intuitive to design, faster to develop, more amenable to modifications, and easier to understand. It leads not only to new ways of constructing programs, but also to new ways of conceiving the programming task.

Nevertheless, object-oriented programming presents some formidable obstacles to those who would like to understand what it's all about or begin trying it out. It introduces a new way of doing things that may seem strange at first, and it comes with an extensive terminology that can take some getting used to. The terminology will help in the end, but it's not always easy to learn. Moreover, there are as yet few full-fledged object-oriented development environments available to try out. It can be difficult to get started.

That's where this book comes in. It's designed to help the reader become familiar with object-oriented programming and get over the hurdle its terminology presents. It spells out some of the implications of object-oriented design and tries to give the reader a flavor of what writing an object-oriented program is really like. It fully documents the Objective-C language, an object-oriented programming language based on standard C, and introduces the most extensive object-oriented development environment currently available -- OpenStep.

Intended Audience:

Because this isn't a book about C, it assumes some prior acquaintance with that language. However, it doesn't have to be an extensive acquaintance. Object-oriented programming in Objective-C is sufficiently different from procedural programming in standard C that the reader won't be hampered if he/she is not an experienced C programmer.

View/Download Object-Oriented Programming And The Objective-C Language | Download from gnustep.org

read more

Object Oriented Analysis and Design - Course Notes

Object modelling is useful for designing computer systems, whether those systems are to be implemented in object-oriented languages or not. Most designs are likely to need more than an object-oriented language, such as a database. Therefore, do not think that this is a wasted exercise if you cannot convince your manager to let you use C++, Smalltalk or whatever flavour of the month language is out there.

Object modelling also has a use outside of the design of computer systems. It is an excellent analysis method, and it can be used in business process reengineering, in social science research, or any complex environment where it is important to capture the structure and functionality of some world.

This course aims to provide you with:

1. A simple, clear, analysis and design notation.
2. A good basic understanding of the concepts of object oriented systems.
3. A method for construction of analyses and designs.
4. Some discussion of the implementation of designs.

View/Download Object Oriented Analysis and Design - Course Notes

read more

Learning Object Oriented Programming with Delphi

An object is a separate, self-contained, encapsulated entity, and the term encapsulation is important in OO. This means that an object has data that it can keep private from the outside world and that it has specific behaviour. It manipulates its data and implements its behaviour through its methods.

Writing the code that defines an object's methods has many similarities with structured programming, and so uses many structured programming principles such as structured selection (If..then..else, Case) and repetition (While..do and For loops).

In this module we assume that students are familiar with these concepts and so concentrate on principles that apply specifically to OO programming.

Delphi as a Learning Environment:

This course uses Delphi to teach object orientation. Delphi's roots lie in Pascal, and so it has a sound, structured foundation. It is also strongly object oriented and provides many OO characteristics such as class inheritance, static binding and dynamic binding, and reference semantics.

The module makes extensive use of graded, worked examples to give students hands-on experience in the implementation of OO code. This helps to bridge the gap between the seemingly simple OO principles and the ramifications of these principles in practice. Through the inductive sequencing of concepts and through the extensive use of worked examples, this module strongly supports independent study, and has been prepared with distance learning students in mind.

In the first two chapters of this module we use Delphi's RAD facilities to start exploring various aspects of OO.

Then we apply these same principles to code that we ourselves write. We start exploring how to define and instantiate classes by looking at the way Delphi builds up a 'Form', which is the name Delphi uses for a window in a graphical interface environment.

Author : John Barrow; edited by Zarko Gajic
Publication Date : November 2007

View/Download Learning Object Oriented Programming with Delphi

read more

Seamless Object-Oriented Software Architecture - Analysis And Design of Reliable Systems

This book shows how a consistent set of object-oriented abstractions can be applied throughout the entire software construction process, based on three major ideas: seamlessness, reversibility, and contracting.

Seamlessness, as in the first word of the title, follows from the observation that the similarities between the tasks to be carried out at the various steps of a project far outweigh their inevitable differences, making it possible to obtain a continuous process that facilitates communication between the various actors involved, ensures a direct mapping between a problem and its software solution, and results in a high level of quality for the final product.

Reversibility means that the seamless procedure must work in both directions: if one modifies a system that has already reached the implementation phase - a frequent case in practice - it must be possible to reflect the modification back to the higher levels of design, specification, and analysis.

The contract model was introduced to a wider audience as early as 1988 by Bertrand Meyer in his introductory book Object-Oriented Software Construction (OOSC), which quickly became, and still is, the standard reference on basic object-oriented concepts. In a sense, this book is a continuation of OOSC, carrying some of its software engineering ideas to their logical conclusion in the area of analysis and design. The result is a method called BON (Business Object Notation) which contains a set of concepts and corresponding notations to support object-oriented modeling centered around the three principles of seamlessness, reversibility, and software contracting.

Intended Audience:

The book is intended for software professionals as well as for students at the graduate and undergraduate levels. This book can be read by anyone who has acquired a general understanding of the problems of software engineering, and who has some inclination for abstract thinking.

Author : Kim Waldén and Jean-Marc Nerson
Publication Date : September 1994
Publisher : Prentice Hall

View/Download Seamless Object-Oriented Software Architecture - Analysis And Design of Reliable Systems | Book's Webpage

read more

Objective-C 2.0 Essentials

On the surface this sounds like an odd opening sentence for a programming book. After all, if this were a book about JavaScript or PHP I'd be safe in assuming that you planned to develop some kind of web site or web application. Similarly, if this were a Visual Basic book it'd be a good bet that you had plans to write a Windows application. Indeed, had I asked this question a few years ago, I could have guessed with a reasonable level of confidence that you wanted to learn Objective-C in order to develop some software to run on Apple's Mac OS X operating system. Now, however, there is a greater likelihood that you plan to develop an application to run on the iPhone.

The iPhone, after all, runs a special version of Mac OS X. Given that Objective-C is the programming language of choice for this operating system it should come as no surprise that before you can develop iPhone applications you first need to learn how to program in Objective-C.

The objective of this book is to teach the skills necessary to program in Objective-C using a style that is easy to follow, rich in examples and accessible to those who have never used Objective-C before. Topics covered include the fundamentals of Objective-C such as variables, looping and flow control. Also included are details of object oriented programming, working with files and memory and the Objective-C Foundation framework.

Those who have developed using other programming languages such as C, C++, C# or Java will find much about Objective-C that is familiar. That said, there are aspects of the language syntax that are unique to Objective-C. Even experienced programmers should therefore expect to spend some time transitioning to this increasingly popular programming language before embarking on a major development project.

Whatever your background and experience, we have worked hard to make this book as useful and helpful as possible as you traverse the Objective-C learning curve.

Author : Neil Smyth
Publication Date : January 2010

View/Download Objective-C 2.0 Essentials

read more

Object-Oriented System Development

Object-Oriented System Development is written for professionals involved in the development of medium, large, and distributed systems. Rather than subscribing to a particular object-oriented method, the authors give instructions on how to put key object-oriented concepts to work in software construction. Many examples, including a full banking system, are developed throughout the book to illustrate the process of object-oriented software development from analysis, through design and into implementation.

Each chapter concludes with exercises. Although one can read this book while bypassing the exercises, they are recommended. Some exercises ask you to operationalize the concepts in this book. Others are quick 'thought questions', sometimes even silly sounding ones, that may lead you into territory that you have not explored.

Author(s) : Dennis de Champeaux, Douglas Lea, and Penelope Faure
Publication date : May 1993
ISBN : 0-201-56355-X
Pages : 532
Publisher : Addison-Wesley Pub Co

View/Download Object-Oriented System Development

read more

Object-Oriented Software Composition

Object-Oriented Software Composition adopts the viewpoint that object-oriented technology is essentially about composing flexible software applications from software components. Although object-oriented languages, tools and methods have come a long way since the birth of object-oriented programming, the technology is not yet mature. This book presents the results of a series of research projects related to object-oriented software composition that were carried out within the Object Systems Group at the University of Geneva, or by partners in collaborative research projects, during a period of about ten years. As such, this book is an attempt to synthesize and juxtapose ideas that were developed by a group of people working closely together over several years.

Although many different topics are treated, by presenting them together, the authors intend to show how certain ideas and principles are closely related to software composition, whether one considers programming language design, formal specification, tools and environments, or application development. Common threads running throughout the book include plug compatibility as a way of formalizing valid ways of composing components, active objects as being fundamental to the development of open systems, protocols as a necessary aspect of plug compatibility for active objects, higher-order functional composition as complementary to object composition, and evolution of objects and object frameworks as an essential aspect to capture in the software lifecycle.

This book should appeal to researchers and practitioners familiar with object-oriented technology, who are interested in research trends related to software composition. Although this book was not designed as a textbook, it would be suitable for an advanced seminar on object-oriented research. Individual chapters can be read independently. The order of presentation has been selected mainly to illustrate a progression of ideas from programming language design issues to environments and applications. Not only is the "Geneva view" of object-oriented development presented, but considerable effort has gone into placing the work in context, and several of the chapters contain extensive surveys of related work.

Author(s): Oscar Nierstrasz and Dennis Tsichritzis
Publication Date: 1995
Publisher: Prentice Hall

View/Download Object-Oriented Software Composition | Book's homepage | SCG Archive

read more

A Practical Introduction to Data Structures and Algorithm Analysis Third Edition (C++ Version)

This document is made freely available for educational and other non-commercial use. You may make copies of this file and redistribute it without charge. You may extract portions of this document provided that the front page, including the title, author, and this notice are included. Any commercial use of this document requires the written consent of the author.

We study data structures so that we can learn to write more efficient programs. But why must programs be efficient when new computers are faster every year? The reason is that our ambitions grow with our capabilities. Instead of rendering efficiency needs obsolete, the modern revolution in computing power and storage capability merely raises the efficiency stakes as we computerize more complex tasks.

The quest for program efficiency need not and should not conflict with sound design and clear coding. Creating efficient programs has little to do with "programming tricks" but rather is based on good organization of information and good algorithms. A programmer who has not mastered the basic principles of clear design is not likely to write efficient programs. Conversely, "software engineering" cannot be used as an excuse to justify inefficient performance. Generality in design can and should be achieved without sacrificing performance, but this can only be done if the designer understands how to measure performance and does so as an integral part of the design and implementation process. Most computer science curricula recognize that good programming skills begin with a strong emphasis on fundamental software engineering principles. Then, once a programmer has learned the principles of clear program design and implementation, the next step is to study the effects of data organization and algorithms on program efficiency.

Author : Clifford A. Shaffer, Department of Computer Science, Virginia Tech
Publication Date : January 2010

View/Download A Practical Introduction to Data Structures and Algorithm Analysis Third Edition (C++ Version)

read more

Algorithmic Problem Solving

In historical terms, the digital computer is very, very new. The science of computing is yet newer. Compared to its older sister - mathematics - which is thousands of years old, it is hardly in the embryonic stage of development. Yet, computing science is already having a major influence on our problem-solving skills, amounting to a revolution in the art of effective reasoning.

Because of the challenges of programming (which means instructing a dumb machine how to solve each instance of a problem) and the unprecedented scale of programming problems, computing scientists have had to hone their problem-solving skills to a very fine degree. This has led to advances in logic, and to changes in the way that mathematics is practised. This book forms an introduction to problem-solving using the insights that have been gained in computing science.

Solutions to programming problems are formulated as so-called algorithms. An algorithm is a well-defined procedure, consisting of a number of instructions, that are executed in turn in order to solve the given problem.

Normally, an algorithm will have certain inputs; for each input, the algorithm should compute an output which is related to the input by a certain so-called input-output relation. Formulating an algorithm makes problem-solving decidedly harder, because it is necessary to formulate very clearly and precisely the procedure for solving the problem. The more general the problem, the harder it gets. The advantage, however, is a much greater understanding of the solution. The process of formulating an algorithm demands a full understanding of why the algorithm is correct.

Intended Audience:
This book aims to impart these new skills and insights to a broad audience, using an example-driven approach. It aims to demonstrate the importance of mathematical calculation, but the chosen examples are typically not mathematical; instead, they are problems that are readily understood by a lay person, with only elementary mathematical knowledge. The book also aims to challenge; most of the problems are quite difficult, at least to the untrained or poorly trained practitioner.

Author : Roland Backhouse, School of Computer Science and Information Technology, University of Nottingham
Publication Date : June 2006

View/Download Algorithmic Problem Solving | Exercises, Coursework and Model Solutions

read more

Computational Modeling and Complexity Science

This book is about data structures and algorithms, intermediate programming in Python, complexity science and the philosophy of science:

Data structures and algorithms:
A data structure is a collection that contains data elements organized in a way that supports particular operations. For example, a dictionary organizes key-value pairs in a way that provides fast mapping from keys to values, but mapping from values to keys is generally slower.

An algorithm is an mechanical process for performing a computation. Designing efficient programs often involves the co-evolution of data structures and the algorithms that use them. For example, the first few chapters are about graphs, a data structure (nested dictionaries) that is a good implementation of a graph, and several graph algorithms that use this data structure.

Python programming:
This book picks up where Think Python leaves off. I assume that you have read that book or have equivalent knowledge of Python. As always, I will try to emphasize fundmental ideas that apply to programming in many languages, but along the way you will learn some useful features that are specific to Python.

Computational modeling:
A model is a simplified description of a system that is useful for simulation or analysis. Computational models are designed to take advantage of cheap, fast computation.

Philosophy of science:
The models and results I will present raise a number of questions relevant to the philosophy of science, including the nature of scientific laws, theory choice, realism and instrumentalism, holism and reductionism, and Bayesian epistemology.

There are two kinds of computational models:

Continuous:
Many computational models compute discrete approximations of equations that are continuous in space and time. For example, to compute the trajectory of a planet, you could describe planetary motion using differential equations and then compute a numerical approximation of the position of the planet at discrete points in time.

The fields of numerical methods and scientific computing tend to focus on these kinds of models.

Discrete:
Discrete models include graphs, cellular automata, and agent-based models. They are often characterized by structure, rules and transitions rather than by equations. They tend to be more abstract than continuous models; in some cases there is no direct correspondence between the model and a physical system.

Complexity science is an interdisciplinary field—at the intersection of mathematics, computer science and physics—that focuses on these kinds of models.

And that’s what this book is about.

Author : Allen B. Downey
Publication Date : July 2008

View/Download Computational Modeling and Complexity Science

read more

Algorithms

This book evolved over the past ten years from a set of lecture notes developed by the authors while teaching the undergraduate Algorithms course at Berkeley and U.C. San Diego.

The topics were carefully selected and clustered. No attempt was made to be encyclopedic, and this left more spaces to include topics traditionally de-emphasized or omitted from most Algorithms books.

This book consists of four parts:

Part I starts with the historical beginning, RSA cryptosystem, divide-and-conquer algorithms for integer multiplication, sorting and median finding, as well as the fast Fourier transform.

Part II, the most traditional section of the book, concentrates on data structures and graphs; the contrast here is between the intricate structure of the underlying problems and the short and crisp pieces of pseudocode that solve them.

Part III deals with the "sledgehammers" of the trade, techniques that are powerful and general: dynamic programming (a novel approach helps clarify this traditional stumbling block for students) and linear programming (a clean and intuitive treatment of the simplex algorithm, duality, and reductions to the basic problem).

The final Part IV is about ways of dealing with hard problems: NP-completeness, various heuristics, as well as quantum algorithms, perhaps the most advanced and modern topic. As it happens, this book ends the story exactly where it started it, with Shor's quantum algorithm for factoring.

Intended Audience :
Instead of dwelling on formal proofs, this book distills in each case the crisp mathematical idea that makes the algorithm work. In other words, this book emphasizes rigor over formalism. Undergraduate students in Computer Science should be much more receptive to mathematical rigor of this form.

Author(s) : S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, University of California, San Diego
Publication Date : 22 May 2006

View/Download Algorithms

read more

Algorithms for Programmers

This draft is first created to accompany the already established collection of FXT libraries by the same author, on the fast transforms and low level algorithms. So far there has been 23 chapters of selected algorithms, each contains the necessary theorems and the corresponding code. While some topics (like Fast Fourier Transforms) need a clear and explicit introduction, some others (like the bit wizardry chapter) seem to be best presented by basically showing the code with just a few comments. The pseudo language Sprache is used mainly when the corresponding C++ does not appear to be self-explanatory. Still, larger pieces of code are presented in C++.

The latest 23 chapters so far:
- Bit wizardry
- Permutations
- Sorting and searching
- Data structures
- Combinatorial algorithms
- Searching paths in directed graphs
- The Fourier transform
- Algorithms for fast convolution
- The Hartley transform (HT)
- Number theoretic transforms (NTTs)
- The Walsh transform and its relatives
- The Haar transform
- and 10 chapters on arithmetical algorithms

The theorem parts is presented in a straightforward and point-to-point style, useful for both learning and quick reference purposes. And the implementation source code is kept in a strict and optimized style. And since I'm personally not very fond of devouring algorithm theorems with those curly mathematic notations, I found the source code really helpful in understanding them.

Overall, this is a nice collection of algorithms in a compact and no-nonsense style with reasonably optimized working code and pseudo-code. Definitely will do a great favor for students of computer science.

Since this book is still a draft, the readers are welcome to criticize and make suggestions. Publication is planned for summer 2005.

Author(s) : Jörg Arndt
Last Updated : February 14, 2007
This is a draft -- a work in progress

View/Download Algorithms for Programmers

read more

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

Problems on Algorithms, Second Edition

This book is a collection of problems on the design, analysis, and verification of algorithms. It is for use by practicing programmers who wish to hone and expand their skills, as a supplementary text for students enrolled in an undergraduate or beginning graduate class on algorithms, and as a self-study text for graduate students who are preparing for the qualifying examination on algorithms for a Ph.D. program in Computer Science or Computer Engineering. It is intended to augment the problem sets found in any standard algorithms textbook.

To keep this book's length in a reasonable bounds, the author has made two decisions. The first is to cover only what it considers to be the most important areas of algorithm design and analysis. The second is not to search for the origin of the problems used. A lengthy discussion of the provenance of each problem would help make this book more scholarly, but would not make it more attractive for its intended audience - students and practicing programmers.

Reviews: Amazon.com

"The ultimate purpose of this book is to assist you in understanding how to design and analyze algorithms in general via the solution of problems, not to provide you with every algorithmic technique under the sun. In that purpose I think that it succeeds brilliantly. Just remember that ultimately it is a book of problems. You should look elsewhere for the details of the theory. Highly recommended."

"This is a terrific little book, which I recommend highly to students of computer science, but above all to those who teach computer science."

Problems on Algorithms, Second Edition
Author(s) : Ian Parberry and William Gasarch
Publication date : 2002
Free License : Ian Parberry's Free License

View/Download Problems on Algorithms

read more

Sorting and Searching Algorithms: A Cookbook

This is a collection of algorithms for sorting and searching. Descriptions are brief and intuitive, with just enough theory thrown in.

The first section introduces basic data structures (array and linked list) and timing notation. Readers will be shown the strength and weakness of each choice of data structures.

The next section presents several sorting algorithms. This is followed by techniques for implementing dictionaries, structures that allow efficient search, insert, and delete operations. There exists some algorithms that do all the three operations efficiently.

The last section illustrates algorithms that sort data and implement dictionaries for very large files.

Intended Audience

This cookbook assumes that the reader knows C and familiar with concepts such as arrays and pointers. Source code for each algorithm, in ANSI C, is included.


Sorting and Searching Algorithms: A Cookbook
Author(s) : Thomas Niemann, Portland, Oregon
Publication Date : n/a


View/Download Sorting and Searching Algorithms: A Cookbook | ANSI C source code

read more