Introduction to Data Structures and Algorithms - DSA #1

Information

In January 2025, I started learning Data Structures and Algorithms (DSA) course at my university. I really enjoy learning this course, and I think sharing my notes is the best way to actually deepen my understanding of the topics while discovering new things along the way!

By the way, some of the resources in my notes are adapted from the DSA lectures at the Faculty of Information Technology, University of Science, VNU-HCM.

Here are some of the cool topics I'll be covering throughout this series:

In this note, I'll introduce the fundamentals of data structures and algorithms by defining key concepts and illustrating them with real-life examples and comparisons.

Introduction to Data Structures and Algorithms

Data structures and algorithms, these are the hidden engines that runs our digital world, from how your phone knows how to get you home, to those social media sites like Facebook or TikTok seem to know what you’d like to watch next. What are they, really?

Data Structures

Let's start with data structures. Imagine you have a ton of stuff—you wouldn't just throw everything into a big pile. Instead, you'd want to organize it in a logical way. Maybe you'd put your clothes in the closet or your tools in a toolbox. Data structures work the same way: they're methods of organizing information in a computer so it's easy to find and use.

And this is a formal definition of a data structure:

A data structure is a specific way to store and organize data in a computer’s memory so that these data can be used efficiently later.

Imagine someone asked you to write a program to calculate the sum of two integers.

#include <iostream>

int main() {
  int a, b;
  std::cin >> a >> b;
	
  int sum = a + b;
  std::cout << sum;
}

This seems easy, right? But what if you were given a task of calculating the sum of $10^9$ integers? Would you really define $10^9$ separate variables?

That would be incredibly inefficient and tedious. You need a better way to store these $10^9$ integers. This is where the array data structure comes in handy.

#include <iostream>
const int NUMBERS_COUNT = 1e9;

int main() {
  int numbers[NUMBERS_COUNT];
  for (int i = 0; i < NUMBERS_COUNT; i++) {
    std::cin >> numbers[i];
  }
	
  int sum = 0;
  for (int i = 0; i < NUMBERS_COUNT; i++) {
    sum = sum + numbers[i];
  }
  std::cout << sum;
}

See, it’s much easier to calculate the sum of $10^9$ integers now.

You might be wondering, "Why not just add each new integer directly to the $sum$ variable as we type it? That way, we wouldn't need an array at all!"

While that's a valid point, this example simply demonstrates how data structures work. Just as we organize different items in our homes in different ways, we use various data structures in computer science for different purposes.

Some general data structure types includes the array, the file, the record, the linked list, the tree, and so on.

Algorithms

Algorithms are essential in programming. Think of an algorithm as a set of step-by-step instructions to solve a specific problem—similar to a recipe for baking a cake. You follow a specific sequence of steps to achieve the desired result. Just like baking, the order of those steps matter. Each step must be carefully planned to ensure you reach your intended outcome.

This is an informal description of an algorithm:

An algorithm is considered as a step-by-step procedure for solving a problem, especially by a computer in a finite number of steps.

And… a formal definition:

An algorithm is considered a Turing machine—a fancy way of saying it’s a computational process that can solve any solvable problem (if given enough time and resources).

Algorithms vs Computer Programs

Are algorithms and computer programs the same thing?

Although they’re closely related, they’re different from each other.

• An algorithm is an abstract concept—like a blueprint or idea that can be illustrated on paper. Since it's abstract, it can't be "run" directly on a computer. In contrast, a program is a concrete implementation of an algorithm, written in a specific programming language.
• An algorithm is a general solution for a family of problems. For example, the binary search algorithm works on any sorted list to find an element, regardless of its content or size. On the other hand, a program solves a problem for particular inputs and within the constraints of the machine it runs on.
• A program cannot apply to any instance: only to those…
  • …which do not go beyond the resource of the machine which runs it (e.g. memory or processing power).
  • …which would not require an execution time exceeding the patience of the programmer - because nobody has infinite patience!

    Imagine a program solving the Tower of Hanoi puzzle with 64 discs, moving one disc per second, would take about 584 billion years to complete—far longer than the age of the universe!

Why are good algorithms so important? Can't any algorithm eventually get the job done?

Think of it this way: imagine you have a world-class chef, but you give them a terrible recipe with vague instructions and missing steps. Sure, they might figure it out eventually, but it'll take longer and the result won't be nearly as good.

The same principle applies to computers and algorithms. Even on a supercomputer, a poor algorithm is like that terrible recipe—it'll be slow, inefficient, and produce subpar results. Good algorithms are essential for completing tasks quickly and effectively.

This becomes crucial when handling large amounts of data. An efficient algorithm can dramatically improve a program's speed and performance. As we generate more and more data globally, we need increasingly sophisticated algorithms to process it all. That's why current research focuses heavily on developing more efficient algorithms for applications like machine learning and big data analysis.

“Data Structures + Algorithms = Programs” - Niklaus Wirth

“The greatest singer in the world cannot save a bad song!”
“Supercomputers cannot rescue a bad algorithm!”

Additional Notes

Structured Programming

Problem statement: On a 2D Cartesian plane, there are three line segments, each defined by two endpoints with coordinates $(x_i, y_i)$. Write a program that determines whether the lengths of these three line segments can form the sides of a triangle.

A common first approach to writing this program looks like this:

int main() {
  int xAstart, yAstart, xAend, yAend;
  int xBstart, yBstart, xBend, yBend;
  int xCstart, yCstart, xCend, yCend;
	
  std::cin >> // ... Those 12 variables
	
  float len1 = sqrt(...
  float len2 = ...
  float len3 = ...
	
  if ((len1 < len2 + len3) && (len2 < len1 + len3) && (len3 < len1 + len2)) {
    // Can form a triangle
  } else {
    // Cannot form a triangle
  }
}

Others might take a more structured approach to the code:

struct Point {
  int x, y;
};

struct Line {
  Point s, e;
  float len;
};

int main() {
  Line lines[3];
  for (int i = 0; i < 3; i++) {
    std::cin >> ...
    lines[i].len = sqrt(...
  }
	
  if ((lines[0].len < lines[1].len + lines[2].len) 
      && (lines[1].len < lines[0].len + lines[2].len) 
      && (lines[2].len < lines[0].len + lines[1].len)) {
    // Can form a triangle
  } else {
    // Cannot form a triangle
  }
}

If you write code like this, you’re the SLAVE of your computer instead of the other way around. You're simply asking “Uh hey, I’ve finished writing the code, is this correct?” while the computer casually validates your work.

Remember: you are the MASTER of your computer, not its servant. A better approach is to use conditionals and loops so that your computer has some work to be done while you save a lot of time writing your program, like this:

int main() {
  // ...
  bool canFormTriangle = true;
  for (int i = 0; i < 3; i++) {
    if (lines[i].len + lines[(i + 1) % 3].len <= lines[(i + 2) % 3].len) {
      canFormTriangle = false;
      break;
    }
  }
  
  if (canFormTriangle) {
    // ...
  } else {
    // ...
  }
}

This exemplifies structured programming—an approach that enhances program quality, clarity, and development speed through disciplined use of control flow structures (if/else) and repetition statements (for/while).

Take control of your computer—be its master, not its servant!

👏 Thanks for reading!