Preface
Before there were computers, there were algorithms. But now there are computers, there are even more algorithms, and algorithms have always been the heart of every computer.
With modern computer technologies, we can complete some tasks without knowing much about algorithms, but with a good foundation in algorithms, we can do much more.
In this chapter we will start thinking about the design and analysis of algorithms. It is intended to be a gentle introduction to specifying algorithms, some of the design strategies that will be used throughout this book, and many of the basic ideas used in algorithm analysis.
1.1 Data Structure
A data structure is a specific way of storing and organizing data in a computer so that it can be used efficiently.
1 2 | Một Data Structure là một định dạng đặc biệt để tổ chức và lưu trữ dữ liệu. |
Common types of data structures include arrays, files, linked lists, stacks, queues, trees, graphs, …
Depending on the organization of the elements, data structures are classified into two types:
- Linear data structures : Elements are accessed in sequential order but it is not required to store all elements sequentially (say, Linked Lists). Examples: Linked Lists, Stacks and Queues.
- Non – linear data structures : The elements of this data structure are stored/accessed in a non-linear order. Examples: Trees and graphs.
1.2 Abstract Data Types (ADTs)
Before defining abstract data types, let’s look at different ways of looking at data types from a system perspective.
We all know that, by default, all primitive data types (primitive data types like int, float, ….) support basic operations like addition and subtraction.
The system provides implementations for primitive data types.
For user-defined data types, we also need to define operations.
The implementation for operations can be done when we actually use them.
That means, in general, user defined data types will be user-defined operations for them.
To simplify the problem-solving process, we combine data structures with their operations, and we call these Abstract Data Types (ADTs).
The ADT consists of two parts :
- Declaration of data
- Declaration of operations
Commonly used ADTs: Linked Lists, Stacks, Queues, Priority Queues, Binary Trees, Dictionaries, Disjoint Sets (Union and Find), Hash Tables, Graphs, …
For example, stack uses LIFO (Last-In-First-Out) mechanism while storing data in data structures.
The last element inserted into the stack is the first to be deleted.
While defining the ADT, don’t worry about the implementation details. They only appear when we want to use them.
Different types of ADTs are suitable for different types of applications, and some are highly specialized for specific tasks.
In this series we will go through many of them and you will be able to relate data structures to the type of problems they solve .
1.3 What is an Algorithm?
Let’s consider the problem of preparing an omelette. To prepare the omelette, we follow the steps below:
1 2 3 4 5 6 7 8 | 1. Lấy chảo rán. 2. Lấy dầu. a. Còn dầu không? i. Nếu có, hãy cho dầu vào chảo ii. Nếu hết, ta có đi mua dầu không? 1. Nếu có, ra ngoài và mua. 2. Nếu không, ta kết thúc công việc. |
What we’re doing is, for a given problem (here, preparing an omelet), is providing a step-by-step process for solving it. The algorithm is similar:
1 2 | Một algorithm(giải thuât) là các hướng dẫn rõ ràng từng bước để giải quyết một vấn đề nhất định. |
In the traditional study of algorithms, there are two main criteria for evaluating the value of algorithms:
- correctness : does the algorithm give a solution to the problem in a finite number of steps?
- efficiency : how many resources (in terms of memory and time) are needed to execute