|
Our Father which art in heaven,
Hallowed by thy name.
Thy kingdom come. Thy will be done in earth, as it is in heaven.
Give us this day our daily bread.
And forgive us our debts as we forgive our debtors.
And lead us not into temptation, but deliver us from evil:
For thine is the kingdom, and the power, and the glory, for ever. Amen. ---
The Lord's Prayer
Update Note:
I will revise the whole content of this notes from Chapter 1 until
Chapter 12 using my own wordings... I will remove or rewrite texts that I
have copied from other places (e.g. USACO texts) to avoid copyright issue. I
will also give illustrations and notes to help the readers in understanding
the concepts. This updating project will start now (8 May 2007) and is
expected to finish by end of May 2007 (delayed until end of
June 2007) (delayed again until probably December 2007)
(delayed again... hopefully by early late 2008 I have time to update these pages).
Updating status: suspended at the moment...
Preface
|
These web pages contain a
collection of one branch of Computer Science curricula: the (basic) data structures
and algorithms. It is true that there are many other websites out there explaining the same topic.
That is why, I designed these web pages to be different from them. Rather than
repeating topics that are explained in other websites (which I can simply cite), I
focused the writing on motivations and applications of using certain data
structure or algorithm. Thus, you will see a lot of hands-on examples rather
than going through mundane theories.
I hope that you will gain something new by reading through
all the material
in this website.
Very Important Note:
If you want to copy anything from this website and distribute it either
for profit or non profit,
you need to ask my permission first
and must cite this website. Thanks for your understanding :)
In case you do not know, parts of the (older) content of this website
are already published in Ahmed Shamsul Arefin's book: Art of Programming
Contest.
Please take a look.
If you need to have a printed version of the (older version) of this
website, buy this book. |
 |
Target Audience (Intermediate Programmers)
The reader should have some knowledge in
data structures, algorithms, and programming languages. I will be using
explanations using two main programming languages, C++ (the STL), and C#.
The contents in this website are not targeted for expert programmers.
To gain access to newer and more sophisticated data structures or
algorithms, browse the Internet for other sources.
Acknowledgements
I thanks God, for giving me some talent in
algorithmic and programming skill, without that, all the stuffs that I have
written here will not even exist. I also want to thanks my parents, who forced
me to learn something with my new PC (at that time it was new) long long
time ago, eventually I picked programming book, and since then I am
interested to learn algorithm and programming. I have a lot of friends who
introduced me to programming contest environment, and since then, I have
participated in several contests and gained so much knowledge and
experience. And to a lot others whom I can't name one by one, thanks :).
Steven Halim
Department of Computer Science
National University of Singapore
07 Aug 2008
Data Structures and Algorithms: Motivations and Applications
Table of Contents
The chapters are organized in increasing level of
difficulties. Please read in order.
1. Introduction:
what is algorithm?, what is data structure?, basic skills, where to
practice?
2. Basic Data Structures: Array,
Linked List, Stack, Queue.
3. Basic Algorithms: Brute Force,
Recursion/Backtracking, Divide/Transform and Conquer,
4. Specialized Algorithm 1: Mathematical
Algorithms
5. Specialized Algorithm 2:
Sorting Algorithms
6. Specialized Algorithm 3:
Searching Algorithms
7. Specialized Algorithm 4:
Greedy Algorithms
8. Specialized Algorithm 5:
Dynamic Programming Algorithms
9. Graph Data
Structure and its Algorithms: DFS/BFS, MST, Single/All-Pairs Shortest
Paths, Network Flows
10. Specialized Algorithm 6:
Computational Geometry Algorithms
11.
Advanced Data Structures: Heap, BST, Dictionary, Set, Data Structure
Augmentation, Mix and Match
12. Links to Stochastic Local Search: NP-hardness, exact/complete algorithm,
inexact/local searches
|
References
I am sure most of these books are either available in
your University libraries or you can buy it through
amazon.com. |
|
1 |
 |
Introduction to Algorithms 2nd edition
[CLRS 2001]
Introduction to Algorithms 1st edition [CLR 1990]
by: Thomas H. Cormen, Charles E.
Leiserson, Ronald L. Rivest, Clifford Stein.
I have both version of the book now :)
and have read most of the chapters (~ 70%). This book is
a-must-have (and read) to be a good programmer. |
|
2 |
|
The
Algorithm Design Manual [ADM]
by
Steven S. Skiena (website).
I already have this book, a very good book.
Also a-must-have for
every good programmer. |
|
3 |
 |
Programming Challenges [PC]
by Steven S. Skiena and Miguel Revilla
I also have this book. Really
interesting book.
Get one copy for yourself :) |
|
4 |
 |
Introduction to the Design and
Analysis of Algorithms [DAA]
by Anany Levitin
A book in design and
analysis of algorithms. Have a new algorithm classification
technique and use a lot of puzzles to explain concepts. Try it :). |
|
5 |
 |
Programming Pearls [PP]
by Jon Bentley
A nice programming book :), actually this book is a compilation from
Bentley's writings in Communications of ACM (CACM) Newsletter. |
|
6 |
 |
The Art of Computer Programming,
Volumes 1-3 [ACP]
by Donald E. Knuth
Hard to understand for beginner but worth to read (quite mathematical)
Note: I don't have this book... |
|
7 |
Others |
Anything else related to programming. I have a long list actually,
but the first few books above are already sufficient (even though
most are expensive)... |
This document, index.html, has been accessed 13012 times since 10-Oct-07 11:47:24 SGT.
This is the 12th time it has been accessed today.
A total of 5755 different hosts have accessed this document in the
last 373 days; your host, 38.103.63.60, has accessed it 2 times.
If you're interested, complete statistics for
this document are also available, including breakdowns by top-level
domain, host name, and date.
|
