Algorithms and Data Structures

Books


Design Patterns


YouTube

Sites

GitHub Repositories

Entropy & Information Theory

Code Training

KhanAcademy

Data Structures Visualization

Programming Paradigms

1. Procedural Paradigm

Example in C:

#include <stdio.h>

void sayHello() {
  printf("Hello, World!\n");
}

int main() {
  sayHello();
  return 0;
}

2. Imperative Paradigm

JavaScript Example:

let total = 0;
for (let i = 1; i <= 10; i++) {
  total += i;
}
console.log(total); // 55

3. Functional Paradigm

Elixir Example:

defmodule Math do
  def sum(a, b) do
    a + b
  end
end

IO.puts Math.sum(1, 2) # 3

4. Object-Oriented Paradigm (OOP)

Example in Python:

class Animal:
  def __init__(self, name):
    self.name = name

def speak(self):
  pass

class Dog(Animal):
  def speak(self):
    return f"{self.name} says Woof!"

dog = Dog("Buddy")
print(dog.speak()) # Buddy says Woof!

5. Declarative Paradigm

Example in SQL:

SELECT * FROM products WHERE price > 100;

6. Logical Paradigm

Example in Prolog:

parent(john, mary).
parent(mary, susan).
grandparent(X, Y) :- parent(X, Z), parent(Z, Y).

7. Structured Paradigm

Example in TypeScript:

function factorial(n: number): number {
  if (n <= 1) {
    return 1;
  }
  return n * factorial(n - 1);
}

console.log(factorial(5)); // 120

Summary:

These paradigms help to structure and organize code in different ways, each with its benefits and best applications.

P vs NP Problems

Source: https://www.youtube.com/watch?v=pQsdygaYcE4

Stack vs Heap

Let’s imagine that your computer’s memory is like a bookshelf with several shelves. When you need to store something, you can put it on one of these shelves in two different ways: stack and heap.

Stack

  1. Organization: The stack is like a stack of plates, where you put one plate on top of another. The last plate to be put on is the first to be removed.

  2. Speed: The stack is very fast because the plates (data) are accessed in a specific order (LIFO - Last In, First Out).

  3. Fixed Size: The stack has a fixed size. This means that you can only stack a limited number of plates before the stack becomes full.

  4. Automatic Management: When you put a plate (variable) on the stack, it is automatically removed when it is no longer needed.

Heap

  1. Organization: The heap is like a big pile of toys lying around. You can pick up and put toys anywhere.

  2. Speed: The heap is slower than the stack because you may need to search for free space to put a new toy (data).

  3. Variable Size: The heap can grow and shrink as needed, so you can add lots of toys (data) without worrying too much about space.

  4. Manual Management: When you put a toy in the heap, you need to remember to take it out when you’re done using it. If you forget, memory can get messed up (memory leaks).

Example in C

#include <stdio.h>
#include <stdlib.h>

// Function using the stack
void stackExample() {
  int stackVar = 10; // The variable is stored in the stack
  printf("Variable value in the stack: %d\n", stackVar);
}

// Function using the heap
void heapExample() {
  int *heapVar = (int *)malloc(sizeof(int)); // The variable is stored in the heap
  if (heapVar != NULL) {
    *heapVar = 20;
    printf("Variable value in the heap: %d\n", *heapVar);
    free(heapVar); // Remember to free the memory!
  }
}

int main() {
  stackExample();
  heapExample();
  return 0;
}

Code Explanation

  1. Stack Example:
  1. Heap Example:
img

Dinamic Programming

function hanoiTower(
  n: number,
  source: string,
  auxiliary: string,
  destination: string
): void {
  if (n === 1) {
    console.log(`Move disk 1 from ${source} to ${destination}`);
    return;
  }
  hanoiTower(n - 1, source, destination, auxiliary);
  console.log(`Move disk ${n} from ${source} to ${destination}`);
  hanoiTower(n - 1, auxiliary, source, destination);
}

hanoiTower(5, "A", "B", "C");

Concurrency vs Parallelism

Mutex (Mutual Exclusion)

A mutex is a way to ensure that only one thread or process can access a shared resource at a time. It’s like a key you need to enter a room; if someone is already in the room and has the key, you need to wait.

class Mutex {
  private locked = false;

  async lock() {
    while (this.locked) {
      await new Promise(resolve => setTimeout(resolve, 10));
    }
    this.locked = true;
  }

  unlock() {
    this.locked = false;
  }
}
const mutex = new Mutex();

async function criticalSection() {
  await mutex.lock();
  try {
    // Code that accesses the shared resource
    console.log("Resource accessed");
  } finally {
    mutex.unlock();
  }
}

criticalSection();
criticalSection();

Semaphore

A semaphore is a variable used to control access to multiple resources. It can be incremented and decremented and has a maximum limit.

class Semaphore {
  private counter: number;
  private waiting: (() => void)[] = [];

  constructor(counter: number) {
    this.counter = counter;
  }

  async wait() {
    if (this.counter > 0) {
      this.counter--;
    } else {
      await new Promise<void>(resolve => this.waiting.push(resolve));
    }
  }

  signal() {
    if (this.waiting.length > 0) {
      const resolve = this.waiting.shift();
      resolve?.();
    } else {
      this.counter++;
    }
  }
}

const semaphore = new Semaphore(2);

async function accessResource() {
  await semaphore.wait();
  try {
    // Code that accesses shared resources
    console.log("Resource accessed");
  } finally {
    semaphore.signal();
  }
}

accessResource();
accessResource();
accessResource();

Deadlock

A deadlock happens when two or more threads get stuck waiting for each other to release resources, and neither can continue.

const mutexA = new Mutex();
const mutexB = new Mutex();

async function task1() {
  await mutexA.lock();
  console.log("Task 1: Locked A");
  await new Promise(resolve => setTimeout(resolve, 100)); // Simulate some operation
  await mutexB.lock();
  console.log("Task 1: Locked B");
  mutexB.unlock();
  mutexA.unlock();
}

async function task2() {
  await mutexB.lock();
  console.log("Task 2: Locked B");
  await new Promise(resolve => setTimeout(resolve, 100)); // Simulate some operation
  await mutexA.lock();
  console.log("Task 2: Locked A");
  mutexA.unlock();
  mutexB.unlock();
}

task1();
task2();
img

Race Condition

A race condition occurs when the outcome of the software depends on the sequence or timing of uncontrolled events. This usually occurs when two or more threads or processes access and modify a shared resource at the same time.

let counter = 0;

async function increment() {
  const temp = counter;
  await new Promise(resolve => setTimeout(resolve, 100)); // Simulate some operation
  counter = temp + 1;
}

increment();
increment();
increment();

setTimeout(() => {
  console.log(counter); // May not be 3 due to race condition
}, 500);

To avoid race conditions, we use mutexes or other forms of synchronization.

Summary:

These concepts are fundamental to managing concurrency in multithreaded systems.

img

Process vs Threads

Processes:

Threads:

Main differences

Usage examples with TypeScript and Node.js

Process Example: Let’s say you want to run a large script that will take a long time. Instead of doing it in the same program, you can create a new process for it.

import { fork } from "child_process";

// Create a new process to run the script 'longTask.ts'
const newProcess = fork("longTask.ts");

newProcess.on("message", message => {
  console.log("Message from child process:", message);
});

newProcess.send("Start heavy task");

Thread Example: If you want to do several things at the same time within the same program, you can use threads (in Node.js, we use “worker threads”).

import { Worker } from "worker_threads";

// Function that creates a new worker
function runService(workerData: any) {
  return new Promise((resolve, reject) => {
    const worker = new Worker("./workerTask.js", { workerData });
    worker.on("message", resolve);
    worker.on("error", reject);
    worker.on("exit", code => {
      if (code !== 0) {
        reject(new Error(`Worker stopped with code ${code}`));
      }
    });
  });
}
// Call the worker with the necessary data
runService("Data for the worker")
  .then(result => {
    console.log("Worker result:", result);
  })
  .catch(err => {
    console.error(err);
  });

When to use each

So, processes and threads help you do more things at the same time in your program, but in different ways. Processes are more isolated and safe, while threads are faster and more collaborative.

img img

Memory Leaks

Imagine you’re playing a block game, where you build things with toy blocks. Each time you pick up a block, you have to return it to the box when you’re done using it. A memory leak is like you pick up blocks from the box, but never return them. Over time, the box becomes empty and you’re left with no blocks to play with, even though there are still plenty of blocks scattered around the floor.

In programming, a memory leak happens when a program reserves memory to use (like picking up blocks from the box), but doesn’t release that memory when it’s done (like not returning the blocks). This causes the computer’s available memory to gradually decrease, which can cause the program or even the computer to crash.

Examples in Different Languages

Python

Python usually manages memory for you, but you can get memory leaks by keeping unnecessary references to objects.

class Block:
  def __init__(self):
  self.data = [0] * 1000000 # too much data, too much memory!

def create_blocks():
  blocks = []
  while True: # infinite loop!
  blocks.append(Block()) # we keep creating blocks and never freeing them

create_blocks()

TypeScript

In TypeScript, a memory leak can happen when you create objects and never remove references to them.

class Block {
  data: number[];

  constructor() {
    this.data = new Array(1000000).fill(0); // too much data, too much memory!
  }
}

const blocks: Block[] = [];

function createBlocks() {
  setInterval(() => {
    blocks.push(new Block()); // we keep creating blocks and never free them
  }, 1000);
}

createBlocks();

C

In C, you have to manually manage memory allocation and freeing.

#include <stdlib.h>

typedef struct {
  int *data;
} Block;

void create_blocks() {
  while (1) { // infinite loop!
  Block *block = (Block *)malloc(sizeof(Block));
  block->data = (int *)malloc(1000000 * sizeof(int)); // lots of memory allocated
  // we never free the memory allocated with free()
}
}

int main() {
  create_blocks();
  return 0;
}

Rust

Rust helps prevent memory leaks with its memory management system, but they can still happen in certain cases.

struct Block {
  data: Vec<i32>,
}

fn create_blocks() {
  let mut blocks = Vec::new();
  loop {
    let block = Block { data: vec![0; 1_000_000] }; // lots of memory allocated
    blocks.push(block); // we keep creating blocks and never freeing them
  }
}

fn main() {
  create_blocks();
}

In short

A memory leak is like taking toy blocks and never putting them back in the box. In programming, it is reserving memory and never freeing it. This can leave the computer with no available memory, causing programs and the computer itself to crash.

What are Pointers?

Imagine that you have a treasure hidden on a map. The pointer is like an “arrow” that points to the location of the treasure on the map. In programming, a pointer is something that points to a place in the computer’s memory where a value is stored.

Passing by Value vs. Passing by Reference

Passing by Value

Imagine that you have a toy and you lend it to a friend. Instead of giving the actual toy, you give an exact copy of the toy. Now, if your friend breaks the toy, your actual toy is still safe.

In programming, passing by value means giving a copy of the data to a function. If the function modifies the copy, the original data remains unchanged.

Passing by Reference

Now, imagine that you lend your actual toy to your friend. If he breaks the toy, your actual toy will be broken.

In programming, passing by reference means giving the location (or address) of the data to a function. If the function modifies the data, the original data is changed.

Examples in TypeScript and C

TypeScript

Passing by Value

In TypeScript, primitive types (like numbers) are passed by value.

function changeValue(x: number): void {
  x = 10;
  console.log("Inside function:", x);
}

let originalValue = 5;
console.log("Before function:", originalValue);
changeValue(originalValue);
console.log("After function:", originalValue);

In this example, originalValue is not changed because a copy of originalValue is passed to the changeValue function.

Passing by Reference

In TypeScript, objects are passed by reference.

function changeObject(obj: { value: number }): void {
  obj.value = 10;
  console.log("Inside function:", obj.value);
}

let originalObject = { value: 5 };
console.log("Before function:", originalObject.value);
changeObject(originalObject);
console.log("After function:", originalObject.value);

In this example, originalObject is changed because the changeObject function receives the object reference and directly modifies the value.

C

Passing by Value

In C, primitive types (such as integers) are passed by value.

#include <stdio.h>

void changeValue(int x) {
  x = 10;
  printf("Inside function: %d\n", x);
}

int main() {
  int originalValue = 5;
  printf("Before function: %d\n", originalValue);
  changeValue(originalValue);
  printf("After function: %d\n", originalValue);
  return 0;
}

In this example, originalValue is not changed because a copy of originalValue is passed to the changeValue function.

Passing by Reference

In C, you can pass the reference (address) of a variable using pointers.

#include <stdio.h>

void changeValue(int *x) {
  *x = 10;
  printf("Inside function: %d\n", *x);
}

int main() {
  int originalValue = 5;
  printf("Before function: %d\n", originalValue);
  changeValue(&originalValue);
  printf("After function: %d\n", originalValue);
  return 0;
}

In this example, originalValue is changed because the changeValue function receives a pointer to originalValue and directly modifies the value using the pointer.

Summary

Stack vs Queue

img

Arrays vs Lists

img img

Binary Tress

img

Breadth-First Search (BFS) and Depth-First Search (DFS)

Imagine you are playing an exploration game in a maze. You want to find your way to the treasure. There are two main ways to explore the maze: BFS and DFS.

Think of BFS as if you are exploring the maze layer by layer. First, you look at all the rooms around the room you are in. Then, you go to the next rooms in each direction and do the same thing, and so on. You are expanding your search broadly, layer by layer.

Think of DFS as if you are exploring the maze by going as deep as you can in one path before going back and trying another. You choose a direction and keep going until you can’t go any further, then you go back and choose another direction, and so on. You are exploring one path deeply before trying another.

Examples in TypeScript

Let’s see how to implement BFS and DFS in TypeScript to explore a maze represented by a graph.

BFS in TypeScript

function bfs(graph: { [key: string]: string[] }, start: string): string[] {
  let visited: Set<string> = new Set();
  let queue: string[] = [start];
  let result: string[] = [];

  while (queue.length > 0) {
    let node = queue.shift()!;
    if (!visited.has(node)) {
      visited.add(node);
      result.push(node);
      queue.push(...graph[node]);
    }
  }
  return result;
}

// Usage example
const graphBFS = {
  A: ["B", "C"],
  B: ["D", "E"],
  C: ["F"],
  D: [],
  E: ["F"],
  F: [],
};

console.log(bfs(graphBFS, "A"));
// Output: ["A", "B", "C", "D", "E", "F"]

DFS in TypeScript

function dfs(graph: { [key: string]: string[] }, start: string): string[] {
  let visited: Set<string> = new Set();
  let stack: string[] = [start];
  let result: string[] = [];

  while (stack.length > 0) {
    let node = stack.pop()!;
    if (!visited.has(node)) {
      visited.add(node);
      result.push(node);
      stack.push(...graph[node]);
    }
  }

  return result;
}

// Usage example
const graphDFS = {
  A: ["B", "C"],
  B: ["D", "E"],
  C: ["F"],
  D: [],
  E: ["F"],
  F: [],
};

console.log(dfs(graphDFS, "A")); // Output: ["A", "C", "F", "B", "E", "D"]

Summary

In the example:

Big O Notation

const accessElementAtIndex = (
  arr: number[],
  index: number
): number | undefined => {
  // Check if index is within bounds of the array
  if (index >= 0 && index < arr.length) {
    return arr[index]; // Return the element at the specified index
  } else {
    return undefined; // Return undefined if index is out of bounds
  }
};

// Example usage
const array = [2, 5, 8, 12, 16];
const index = 2;
const element = accessElementAtIndex(array, index);

if (element !== undefined) {
  console.log(`Element at index ${index}:`, element);
} else {
  console.log(`Index ${index} is out of bounds`);
}

const binarySearch = (arr: number[], target: number): number => {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    // Check if target is present at mid
    if (arr[mid] === target) {
      return mid;
    }

    // If target is greater, ignore left half
    if (arr[mid] < target) {
      left = mid + 1;
    }
    // If target is smaller, ignore right half
    else {
      right = mid - 1;
    }
  }

  // Element is not present in array
  return -1;
};

// Example usage
const array = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
const target = 72;
const index = binarySearch(array, target);
if (index !== -1) {
  console.log(`${target} found at index ${index}`);
} else {
  console.log(`${target} not found in the array`);
}

const findMax = (arr: number[]): number | undefined => {
  if (arr.length === 0) {
    return undefined; // Return undefined if array is empty
  }

  let max = arr[0]; // Assume the first element is the maximum

  // Iterate through the array to find the maximum element
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) {
      max = arr[i]; // Update max if current element is greater
    }
  }

  return max;
};

// Example usage
const array = [2, 5, 8, 12, 16, 9, 4];
const maxElement = findMax(array);

if (maxElement !== undefined) {
  console.log("Maximum element:", maxElement);
} else {
  console.log("Array is empty");
}

// Function to merge two sorted arrays
const merge = (left: number[], right: number[]): number[] => {
  let result: number[] = [];
  let leftIndex = 0;
  let rightIndex = 0;

  // Merge elements from left and right arrays in sorted order
  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }

  // Concatenate the remaining elements from left or right
  return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
};

// Merge Sort function
const mergeSort = (array: number[]): number[] => {
  if (array.length <= 1) {
    return array;
  }

  // Divide the array into halves
  const mid = Math.floor(array.length / 2);
  const left = array.slice(0, mid);
  const right = array.slice(mid);

  // Recursively sort both halves and merge them
  return merge(mergeSort(left), mergeSort(right));
};

// Example usage
const array = [38, 27, 43, 3, 9, 82, 10];
console.log("Original array:", array);
const sortedArray = mergeSort(array);
console.log("Sorted array:", sortedArray);

const bubbleSort = (array: number[]): number[] => {
  const n = array.length;
  // Outer loop for each pass through the array
  for (let i = 0; i < n - 1; i++) {
    // Inner loop to compare adjacent elements and swap if necessary
    for (let j = 0; j < n - 1 - i; j++) {
      // Swap elements if they are in the wrong order
      if (array[j] > array[j + 1]) {
        // Swap array[j] and array[j + 1]
        const temp = array[j];
        array[j] = array[j + 1];
        array[j + 1] = temp;
      }
    }
  }
  return array;
};

// Example usage
const array = [38, 27, 43, 3, 9, 82, 10];
console.log("Original array:", array);
const sortedArray = bubbleSort(array);
console.log("Sorted array:", sortedArray);

const fibonacci = (n: number): number => {
  if (n <= 1) {
    return n;
  }
  return fibonacci(n - 1) + fibonacci(n - 2);
};

// Example usage
const n = 6; // Calculate Fibonacci number at position 6
console.log(`Fibonacci number at position ${n}:`, fibonacci(n));

// The provided implementation of the traveling salesman algorithm using a brute-force approach has a time complexity of O(n!), where n is the number of points.

// Here's the breakdown:

// Permutations Generation: Generating all possible permutations of the points requires O(n!) time complexity because there are n! permutations for n points.
// Total Distance Calculation: For each permutation, the total distance is calculated, which requires traversing through all points once. This takes O(n) time.
// Finding Shortest Route: After calculating the total distance for each permutation, the shortest route is found by comparing the distances. This takes O(n!) time because there are n! permutations to check.
// Therefore, the overall time complexity of the algorithm is O(n! * n) ≈ O(n!).

// The space complexity mainly comes from storing the permutations and is also O(n!), as it involves storing all possible permutations of the points.

interface Point {
  x: number;
  y: number;
}

function distance(point1: Point, point2: Point): number {
  const dx = point1.x - point2.x;
  const dy = point1.y - point2.y;
  return Math.sqrt(dx * dx + dy * dy);
}

function permute<T>(arr: T[]): T[][] {
  const permutations: T[][] = [];

  function generate(current: T[], remaining: T[]): void {
    if (remaining.length === 0) {
      permutations.push(current);
    } else {
      for (let i = 0; i < remaining.length; i++) {
        const next = current.concat([remaining[i]]);
        const rest = [...remaining.slice(0, i), ...remaining.slice(i + 1)];
        generate(next, rest);
      }
    }
  }

  generate([], arr);
  return permutations;
}

function calculateTotalDistance(route: number[], points: Point[]): number {
  let totalDistance = 0;
  for (let i = 0; i < route.length - 1; i++) {
    totalDistance += distance(points[route[i]], points[route[i + 1]]);
  }
  totalDistance += distance(points[route[route.length - 1]], points[route[0]]);
  return totalDistance;
}

function findShortestRoute(points: Point[]): number[] {
  const numPoints = points.length;
  let shortestDistance = Infinity;
  let shortestRoute: number[] = [];

  const permutations = permute([...Array(numPoints).keys()]);

  for (let i = 0; i < permutations.length; i++) {
    const currentDistance = calculateTotalDistance(permutations[i], points);
    if (currentDistance < shortestDistance) {
      shortestDistance = currentDistance;
      shortestRoute = permutations[i];
    }
  }

  return shortestRoute;
}

function generateRandomPoints(
  numPoints: number,
  minX: number,
  maxX: number,
  minY: number,
  maxY: number
): Point[] {
  const points: Point[] = [];
  for (let i = 0; i < numPoints; i++) {
    const x = Math.floor(Math.random() * (maxX - minX + 1)) + minX;
    const y = Math.floor(Math.random() * (maxY - minY + 1)) + minY;
    points.push({ x, y });
  }
  return points;
}

const numPoints = 10,
  minX = 0,
  maxX = 10,
  minY = 0,
  maxY = 10;

const points = generateRandomPoints(numPoints, minX, maxX, minY, maxY);
const shortestRoute = findShortestRoute(points);
console.log("Shortest Route:", shortestRoute);
console.log(
  "Shortest Distance:",
  calculateTotalDistance(shortestRoute, points)
);
img img img