DEV Community: Cris

Open Source Licenses- All You Need To Know And More

Cris — Sat, 09 Dec 2023 01:42:34 +0000

What are Open Source Licenses?

Open source licenses are legal agreements that define how software can be used, modified, and distributed. They grant specific permissions to users, ensuring that the source code is accessible and can be freely shared. While engineering teams once relied primarily on proprietary code, open source now comprises more than 90% of the components of modern applications.

The whole idea behind the Free and Open movements is basically giving it as a gift to everyone out there. There are some terms, usually a small request to give you some credit (usually a "hey, it's from me" kind of thing), but the whole point is to share the goodness. This Open Source Definitiongoes onto more detail on what it all entails.

Exceptions

I Can Restrict It, Right? Right??

You can if you prefer, but one of the main advantages of open source code is its visibility, which makes it easier to troubleshoot problems and to understand better how something works when the documentation is either lacking or incorrect.

Depending on the type of open source license, you may even be allowed to modify the original source code to tailor it to your needs or fix any issues you find. The license will determine whether this is possible, and under what terms. For example, you may be required to make any modifications publicly available.

What you can't do is put on restrictions like "no commercial use" and still label your project as open-source. As the copyright holder, you've got the power to limit any use of your software or keep it all to yourself. It's your call. However, the Open Source movement is all about spreading the love without too many strings attached. You can put some rules on your software, sure, but if you go overboard, it's hard to call it genuinely open-source. Share the code, embrace the freedom!

I Discovered a project labeled as open-source, but it imposes limitations on commercial usage.

If you stumble upon a project claiming to be open-source while restricting commercial use, they're not playing by the rules—whether intentionally or not. Feel free to point them to this info. Some folks mistakenly use "open source" interchangeably with "source-available", but according to the OG open-source movement, there's a nuance. True open source means no heavy restrictions on how the software is used. Keep it free, keep it open!

That said there is a third option that is gaining traction—open-core service, combining open and closed sources characteristics.

Open-core

Open core adopts a distinct approach. This relatively new model exposes core functionalities to the public, encouraging collaboration, while reserving advanced features behind a paywall. It represents a hybrid model, enhancing accessibility while ensuring a sustainable business framework.
You can read further on it here Open source vs open core what is the difference

Types

There are over 200 open source licenses available, but most open source software falls under a handful of commonly used licenses. These licenses can be broadly categorized into two primary types: copyleft and permissive licenses.

Copyleft: Copyleft licenses - require that any modifications or derivative works of the original open source code inherit the same license terms. This ensures that subsequent versions of the software also remain open source. Examples of popular copyleft licenses include the GNU General Public License (GPL) and the Affero General Public License (AGPL).
- Copyleft licenses have lower usage:
- The GPL family of licenses, including GPL-2, GPL-3, AGPL-3, and LGPL-3, only make up around 5% of the overall license usage.
- This may be due to the restrictions imposed by copyleft licenses on the distribution of derived works.
Permissive: Permissive licenses - provide more freedom for reuse, modification, and distribution of the software. They allow developers to incorporate the open source code into their own projects without requiring the resulting software to be open source. Examples of permissive licenses include the MIT License and the Apache License
Permissive licenses are commonly used:
- The most common permissive license in open source projects is the MIT license.
- Apache 2.0 and BSD-3 licenses are also widely used, making up about 70% of the projects in the Libraries.io dataset.

But Can I Have 2 Licenses 🤔

You have the option to adopt a dual-license approach, a common model where your software is open-source under a copyleft license. While anyone can use it freely, the copyleft aspect can make commercial use more challenging. Simultaneously, you can offer a closed-source license for more freedom, selling these licenses to those wanting commercial usage rights. It's a win-win scenario for both parties. For example a dual license between CC0 and Apache-2.0 would work really well. CC0 effectively waives all copyright and related rights, including attribution. However, CC0 is less suitable for software, which is why the Apache fallback is recommended, despite some attached conditions.

However like previously mentioned another approach is open core, where essential features are open-source, fostering collaboration, while advanced features as paid add-ons.

To Clarify Open Source vs. Proprietary Software

Open source software (OSS) and proprietary software are two distinct types of software with key differences. Here are the main differences between open source and proprietary software:

1. Development and Licensing:

Open source software is distributed with its source code, allowing users to freely inspect, modify, and distribute the code.
Proprietary software is owned by the individual or company that published it and does not provide access to the source code.

2. Cost:

Open source software is generally free to use and modify, although there may be costs associated with web hosting or server setup.
Proprietary software requires companies to purchase a license, often using a subscription model known as Software as a Service (SaaS).

3. Updates and Maintenance:

Open source software is often community-maintained, with periodic updates and patches.
Proprietary software companies release regular updates with new features and bug fixes.

4. Flexibility:

Open source software provides users with the freedom to use or modify the code as needed.
Proprietary software is less flexible and often comes with restrictions on modification and distribution.

5. Ownership and Support:

Open source software is developed and maintained by a community of contributors.
Proprietary software is developed and maintained by the company or group that published it.

6. Intellectual Property Protections:

Open source software typically has limited intellectual property protections.
Proprietary software offers full intellectual property protections.

7. Examples:

Examples of open source software include Android, Linux, and Firefox.
Examples of proprietary software include Microsoft Office, Adobe Photoshop, and Apple macOS.

Now onto the Licenses 🎢

With over 200 licenses available, let's focus on the ones you're likely to encounter or use in your projects. If you don't find the specific one you're looking for here, I recommend checking the Open Source Initiative's license list for a comprehensive search.

Academic Free License v3.0 (AFL-3.0):
- Type: Permissive
- Pros: A permissive open-source license that allows you to modify and distribute the code as long as you attribute the original work and share your changes under the same license.
- Cons: Less popular than some other licenses.
Apache License 2.0 (Apache-2.0):
- Type: Permissive
- Pros: Well-known, permissive license with clear attribution and notice requirements.
- Cons: Requires including a copy of the license and notices in distribution.
Boost Software License 1.0 (BSL-1.0):
- Type: Permissive
- Pros: Permissive license with simple terms allowing modification.
- Cons: Requires including the license in distribution.
BSD 2-clause "Simplified" license (BSD-2-Clause):
- Type: Permissive
- Pros: Extremely permissive license with simple terms.
- Cons: Requires retaining the original copyright notice.
BSD 3-clause "New" or "Revised" license (BSD-3-Clause):
- Type: Permissive
- Pros: Permissive license with an additional clause for advertising use.
- Cons: May be restrictive for some use cases.
BSD 3-clause Clear license (BSD-3-Clause-Clear):
- Type: Permissive
- Pros: Provides clarity and simplicity, similar to the 3-clause BSD.
- Cons: May not be as widely recognized.
BSD 4-clause "Original" or "Old" license (BSD-4-Clause):
- Type: Permissive
- Pros: Permissive license with an endorsement clause.
- Cons: Endorsement clause may limit usage.
BSD Zero-Clause license (0BSD):
- Type: Permissive
- Pros: Extremely permissive, no restrictions.
- Cons: May not be well-known, uncommon.
Creative Commons license family (CC):
- Type: Permissive (varies by specific CC license)
- Pros: Offers various licenses for creative works with different restrictions.
- Cons: Primarily designed for creative content, not software.
Creative Commons Zero v1.0 Universal (CC0-1.0):
- Type: Permissive
- Pros: Maximizes freedom, dedicates work to the public domain.
- Cons: Not suitable for all software, may not be widely accepted.
Creative Commons Attribution 4.0 (CC-BY-4.0):
- Type: Permissive
- Pros: Attribution-based license, flexible for creative works.
- Cons: May not be suitable for software, requires attribution.
Creative Commons Attribution ShareAlike 4.0 (CC-BY-SA-4.0):
- Type: Permissive (with a share-alike requirement)
- Pros: Encourages shared modifications with attribution.
- Cons: May be restrictive for some software projects.
Do What The F*ck You Want To Public License (WTFPL):
- Type: Permissive
- Pros: Extremely permissive with no restrictions.
- Cons: Not widely recognized.
Educational Community License v2.0 (ECL-2.0):
- Type: Permissive
- Pros: Designed for educational software, allows modification.
- Cons: May not be well-known outside educational contexts.
Eclipse Public License 1.0 (EPL-1.0):
- Type: Copyleft
- Pros: Copyleft license encouraging contribution back to the community.
- Cons: Requires derivative works to be licensed under EPL.
Eclipse Public License 2.0 (EPL-2.0):
- Type: Copyleft
- Pros: Updated version of EPL with similar copyleft requirements.
- Cons: Derivative works must be EPL-licensed.
- Basically:
- Good - Similar to EPL-1.0, updated version.
- Bad - Derivative works must be EPL-licensed.
European Union Public License 1.1 (EUPL-1.1):
- Type: Copyleft but interoperable (non viral) and compatible with other licenses including GPL, AGPL, LGPL, EPL, MPL.
- Pros: Originally designed for EU projects, open-source.
- Cons: May not be known globally.
- Basically:
- Good - Covers remote "communication to the public" (online distribution), widely used in EU, promoted in the 27 Member States according to the 2024 Interoperable Europe Act, available in 23 languages, open-source (OSI and FSF approved).
- Bad - May not be known globally.
GNU Affero General Public License v3.0 (AGPL-3.0):
- Type: Copyleft
- Pros: Strong copyleft license ensuring open access to modified code in network services.
- Cons: May be too restrictive for some projects.
GNU General Public License family (GPL):
- Type: Copyleft
- Pros: Strong copyleft license promoting open-source community.
- Cons: Requires derivative works to be GPL-licensed.
GNU Lesser General Public License family (LGPL):
- Type: Copyleft (with limited copyleft for libraries)
- Pros: A family of copyleft licenses, with different versions (2.1 and 3.0) that allow linking with non-GPL-compatible code.
- Cons: Limited copyleft for libraries, not ideal for some projects.
GNU Lesser General Public License v2.1 (LGPL-2.1):
- Type: Copyleft (with limited copyleft for libraries)
- Pros: Allows linking with non-GPL-compatible code.
- Cons: Less permissive for libraries than some other licenses.
GNU Lesser General Public License v3.0 (LGPL-3.0):
- Type: Copyleft (with limited copyleft for libraries)
- Pros: Updated version of LGPL with similar terms.
- Cons: Limited copyleft for libraries.
ISC (ISC):
- Type: Permissive
- Pros: A permissive open-source license that allows almost unrestricted use, modification, and distribution.
- Cons: May not be widely recognized.
LaTeX Project Public License v1.3c (LPPL-1.3c):
- Type: Permissive
- Pros: Permissive for LaTeX packages.
- Cons: Primarily for LaTeX-related work.
Microsoft Public License (MS-PL):
- Type: Permissive
- Pros: Permissive open-source license from Microsoft.
- Cons: Not recognized by all organizations.
MIT (MIT):
- Type: Permissive
- Pros: Highly permissive, widely recognized.
- Cons: No significant drawbacks for most cases.
Mozilla Public License 2.0 (MPL-2.0):
- Type: Permissive
- Pros: Allows modification and distribution with source code.
- Cons: Requires sharing changes to the code.
Open Software License 3.0 (OSL-3.0):
- Type: Permissive
- Pros: Promotes open-source and specifies distribution terms.
- Cons: Requires sharing modified code.
PostgreSQL License (PostgreSQL):
- Type: Permissive
- Pros: Permissive license for PostgreSQL.
- Cons: Primarily for PostgreSQL-related projects.
SIL Open Font License 1.1 (OFL-1.1):
- Type: Permissive
- Pros: Allows use, modification, and distribution of fonts.
- Cons: Designed for fonts, not software.
University of Illinois/NCSA Open Source License (NCSA):
- Type: Permissive
- Pros: Permissive, designed for open-source software.
- Cons: May not be widely known.
The Unlicense (Unlicense):
- Type: Permissive
- Pros: A license that essentially dedicates code to the public domain, allowing almost unrestricted use, modification, and distribution.
- Cons: Not recognized by all organizations.
zLib License (Zlib):
- Type: Permissive
- Pros: Permissive, minimal restrictions.
- Cons: May not be as well-known as other licenses.

MIT License (MIT): This is one of the most permissive licenses. It's recommended for projects that want to maximize the freedom for users and contributors. It's simple, widely recognized, and used in many popular open-source projects.
Apache License 2.0 (Apache-2.0): It's a permissive license with clear terms. It's well-regarded for larger projects and those involving collaboration with corporations. It requires proper attribution and notice but provides legal protection.
GNU General Public License (GPL): If you want to ensure that derivative works of your project remain open source, GPL is a strong copyleft license. The GPL family includes GPL-2.0 and GPL-3.0, with the latter being the more modern and widely used version.
GNU Lesser General Public License (LGPL): LGPL is ideal for libraries and allows linking with non-GPL-compatible code. It ensures that modifications to the library are open source, but it doesn't extend the copyleft to applications using the library.
Mozilla Public License 2.0 (MPL-2.0): This license strikes a balance between strong copyleft and permissiveness. It's suitable for projects that want to encourage open-source contributions while allowing some proprietary use.
GNU Affero General Public License v3.0 (AGPL-3.0) ✨: AGPL is like the GPL but explicitly covers network-based software. It's recommended for projects that run on servers and want to ensure that any modifications to the code are shared. I actually recommend this blog for further reading on why its good - Why the MIT licensed is much more used than GPL-3
Creative Commons Attribution 4.0 (CC-BY-4.0): This is ideal for creative works like documentation or media files. It requires attribution and is flexible for non-software projects.
Unlicense (The Unlicense): If you want to put your code into the public domain, the Unlicense is recommended. It's incredibly permissive, allowing almost unrestricted use and modification.

Extra: Adding a License to You Repo on GitHub

I don't believe I can do it better than the GitHub docs on this one but a quick run down is:

Go to your repository.
Click on "Add File" and "Create new file" Button.
Type the file name as License.txt or License.md in the input box next to your repository name, a drop down button appears towards right side.
Choose the type of license of your choice.
Click "Review and Submit" button at the right side.
Choose "Commit directly to the main branch."
Click "Commit new file" button at the bottom (Green button)

That was quite a bit! I hope you found the information you were looking for. Thanks for reading, and catch you in the next blog! 🙌

Sources

Unearthing Data Structures & Algorithms: The Essentials Guide. P1

Cris — Wed, 01 Nov 2023 10:52:54 +0000

Data structures are the backbone of problem-solving and acing programming interviews. If you're new to the world of computer science, don't worry! Understanding data structures might seem daunting at first, but with a little guidance, it can be simplified.

Choosing the Right Data Structure

Before we dive into the nitty-gritty of data structures, let's understand the importance of choosing the right one. Each data structure has its strengths and weaknesses, and selecting the appropriate one can significantly impact the performance of your code. We often use Big O notation to measure their efficiency.

Three Key Data Structures You Should Know

To build a solid foundation in data structures, focus on three key ones: arrays, linked lists, and hash tables.

Arrays are fixed in size, making adding elements inefficient at times. However, they excel at retrieving items quickly by computing the item's location inside the array.

Linked lists which consist of nodes with values and pointers are perfect for scenarios where you need to add or remove elements efficiently. However, accessing elements might be a bit slower compared to arrays.

Hash tables, on the other hand, allow for efficient retrieval of values based on keys. They use a hashing function to determine the memory location, making them incredibly fast for data retrieval. While hash tables are powerful, they can suffer from collisions, where two keys hash to the same memory location. But fear not! There are various methods to resolve these collisions and ensure your hash table works flawlessly.

Embracing Data Structures and Algorithms

Data structures and algorithms are the heart and soul of computer science. For instance, the depth-first search is a vital algorithm that's used extensively. Additionally, queues and stacks are efficient data structures employed in breadth-first search and other limited use cases.

Graphs and trees also play a crucial role in computer science. They share similarities with linked lists, where nodes point to other nodes, creating a complex but organized network.

The Power of Binary Search Trees

When it comes to searching efficiently, Binary Search Trees (BSTs) take the crown. With specific rules governing node relationships, traversing a BST allows for quick element location, making it a popular choice in various applications.

Building Your Skills

If you're a beginner looking to improve your skills in data structures and algorithms, practice is key. As you start your search, you'll likely come across platforms like Code Wars and LeetCode, which are excellent for honing your problem-solving abilities. LeetCode, in particular, offers real-world programming interview questions from tech companies.

However, there are even better platforms that use those resources to streamline the learning process. CodeTrack is one such platform, specializing in Code Wars problems. It's managed by a dedicated professor who hosts workshops most Fridays throughout the year, making it a great choice for learning.

Another valuable resource with a focus on LeetCode is Grind75 Tech, "The Interview Handbook. Despite its LeetCode focus, the site provides valuable insights for developers at any skill level.

The Big Picture

Now that we got the base essentials out of the way. We can look further into the horizon and take a peek at some of the most important Algorithms there are. The main goal of an algorithm is to take in input, process it and provide an output that is expected. Algorithms can be classified based on the time and space complexity, the technique used for solving the problem, and the type of problem it solves. Examples of algorithms are sorting, searching, graph traversals, string manipulations, mathematical operations, and many more.

Algorithms we will be going over in this first part of the article

Sorting algorithms: Sorting is a fundamental operation in computer science and there are several efficient algorithms for it, such as quicksort, merge sort and heap sort.
Search algorithms: Searching for an element in a large dataset is a common task and there are several efficient algorithms for it, such as binary search and hash tables.
Graph algorithms: Graph algorithms are used to solve problems related to graphs, such as finding the shortest path between two nodes or determining if a graph is connected.

These algorithms are widely used in various applications and a programmer needs to have a strong understanding of them. So I will try my best to explain them.

Sorting algorithms

Quicksort

Quicksort is a divide-and-conquer algorithm that chooses a “pivot” element from the array and partitions the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.

function quicksort(arr) {  // Define a function called 'quicksort' that takes an array 'arr' as input.
  if (arr.length <= 1) {  // Check if the array has one element or is empty.
    return arr;  // If so, return the array as it's already sorted.
  }
  const pivot = arr[Math.floor(arr.length / 2)];  // Choose the pivot element as the middle element of the array.
  const left = [];  // Create an empty array 'left' to store elements smaller than the pivot.
  const middle = [];  // Create an empty array 'middle' to store elements equal to the pivot.
  const right = [];  // Create an empty array 'right' to store elements greater than the pivot.
  for (let i = 0; i < arr.length; i++) {  // Iterate through the array.
    if (arr[i] < pivot) {  // If the element is smaller than the pivot, add it to the 'left' array.
      left.push(arr[i]);
    } else if (arr[i] === pivot) {  // If the element is equal to the pivot, add it to the 'middle' array.
      middle.push(arr[i]);
    } else {  // If the element is greater than the pivot, add it to the 'right' array.
      right.push(arr[i]);
    }
  }
  // Recursively sort the 'left' and 'right' arrays and concatenate them with 'middle' to get the final sorted array.
  return quicksort(left).concat(middle).concat(quicksort(right));
}
console.log(quicksort([3, 6, 8, 10, 1, 2, 1]));  // Call 'quicksort' with an example array and print the result.

Merge Sort

The merge sort algorithm is a divide-and-conquer algorithm that divides an array in two, sorts the two halves, and then merges them back together.

// Merge Sort Implementation (Recursive)
function mergeSort(unsortedArray) {  // Define a function called 'mergeSort' that takes an unsorted array as input.
  if (unsortedArray.length <= 1) {  // Check if the array has one element or is empty.
    return unsortedArray;  // If so, return the array as it's already sorted.
  }
  const middle = Math.floor(unsortedArray.length / 2);  // Find the middle index of the array.
  const left = unsortedArray.slice(0, middle);  // Create a left subarray by slicing from the start to the middle.
  const right = unsortedArray.slice(middle);  // Create a right subarray by slicing from the middle to the end.
  // Using recursion to combine the left and right
  return merge(
    mergeSort(left),  // Recursively call 'mergeSort' on the left subarray.
    mergeSort(right)  // Recursively call 'mergeSort' on the right subarray.
  );
}
function merge(left, right) {  // Define a function called 'merge' that merges two sorted arrays 'left' and 'right'.
  let resultArray = [];  // Create an empty array to store the merged result.
  let leftIndex = 0;  // Initialize a variable 'leftIndex' to track the index in the 'left' array.
  let rightIndex = 0;  // Initialize a variable 'rightIndex' to track the index in the 'right' array.
 while (leftIndex < left.length && rightIndex < right.length) {  // Continue while there are elements in both 'left' and 'right'.
    if (left[leftIndex] < right[rightIndex]) {  // If the element in 'left' is smaller, add it to the 'resultArray'.
      resultArray.push(left[leftIndex]);
      leftIndex++;
    } else {  // If the element in 'right' is smaller, add it to the 'resultArray'.
      resultArray.push(right[rightIndex]);
      rightIndex++;
    }
  }
  return resultArray
          .concat(left.slice(leftIndex))  // Concatenate any remaining elements from 'left'.
          .concat(right.slice(rightIndex));  // Concatenate any remaining elements from 'right'.
}

Heap Sort

The heap sort algorithm is a comparison-based sorting algorithm that builds a heap from the input elements and then repeatedly extracts the maximum element from the heap and places it at the end of the sorted output array.

// JavaScript program for implementation
// of Heap Sort
// Define a function called 'sort' that takes an array 'arr' as input.
function sort(arr) {
  // Get the length of the array.
  const N = arr.length;
  // Build heap (rearrange array)
  // Start from the middle and move towards the beginning to create a max heap.
  for (let i = Math.floor(N / 2) - 1; i >= 0; i--) {
    heapify(arr, N, i);
  }
  // One by one, extract an element from the heap
  for (let i = N - 1; i > 0; i--) {
    // Swap the current root (maximum value) with the last element.
    [arr[0], arr[i]] = [arr[i], arr[0]];
    // Call max heapify on the reduced heap
    heapify(arr, i, 0);
  }
}
// Define a function called 'heapify' for max heapifying a subtree.
// This function takes an array 'arr', the size of the heap 'N', and an index 'i'.
function heapify(arr, N, i) {
  let largest = i;  // Initialize 'largest' as the root node.
  const l = 2 *i + 1;  // Calculate the index of the left child.
  const r = 2* i + 2;  // Calculate the index of the right child.
  // If the left child is larger than the root, update 'largest'.
  if (l < N && arr[l] > arr[largest])
    largest = l;
  // If the right child is larger than the largest so far, update 'largest'.
  if (r < N && arr[r] > arr[largest])
    largest = r;
  // If 'largest' is not the root, swap them and recursively heapify the subtree.
  if (largest !== i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    heapify(arr, N, largest);
  }
}
// Define a utility function to print the elements of an array.
function printArray(arr) {
  const N = arr.length;
  for (let i = 0; i < N; ++i) {
    console.log(arr[i] + " ");
  }
}
// Create an array to be sorted.
const arr = [12, 11, 13, 5, 6, 7];
const N = arr.length;
// Call the 'sort' function to sort the array.
sort(arr);
console.log("Sorted array is");
// Print the sorted array elements.
printArray(arr);
// This code is contributed by SoumikMondal

Search algorithms

Binary Search

Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the array being searched until the target value is found.

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) {
      return mid; // Found the target, return its index
    } else if (arr[mid] < target) {
      left = mid + 1; // Target is in the right half of the current range
    } else {
      right = mid - 1; // Target is in the left half of the current range
    }
  }
  return -1; // Target not found in the array
}
// Example usage:
const sortedArray = [1, 3, 5, 7, 9, 11, 13, 15, 17];
const targetValue = 9;
const resultIndex = binarySearch(sortedArray, targetValue);
if (resultIndex !== -1) {
  console.log(`Target ${targetValue} found at index ${resultIndex}.`);
} else {
  console.log(`Target ${targetValue} not found in the array.`);
}

In this implementation, the binarySearch function takes a sorted array (arr) and a target value (target) as inputs. It sets two pointers, left and right, initially pointing to the first and last elements of the array, respectively.

It then enters a loop that continues as long as the left is less than or equal to the right. In each iteration, it calculates the middle index (mid) of the current range. If the element at the middle index is equal to the target value, the function returns the index. If the target value is less than the element at mid, it updates right to search in the left half of the current range; otherwise, it updates left to search in the right half.

If the loop exits without finding the target value, the function returns -1 to indicate that the target value is not present in the array.

The example usage demonstrates searching for the target value 9 in the sorted array. If the target value is found, it prints the index where it was found; otherwise, it indicates that the target value is not present in the array.

Hash Tables

A hash table is a fundamental data structure that plays a crucial role in many aspects of programming. To gain a deeper understanding of how it works and its practical applications, I highly recommend watching this informative video.

// In this example, the chaining method, also known as closed addressing,
// was used to deal with collisions.
class HashTable {
    constructor() {
        this.table = new Array(127);  // Create an array with a length of 127 (to represent ASCII symbols).
        this.size = 0;  // Initialize the size of the hash table to 0.
    }
    _hash(key) {  // Define a hash function to compute the index for a given key.
        let hash = 0;
        key = key.toString();
        for (let i = 0; i < key.length; i++) {
            hash += key[i].charCodeAt();  // Calculate the sum of character codes in the key.
        }
        return hash % this.table.length;  // Return the hash value within the table's length.
    }
    loadFactor() {  // Calculate the load factor (size / table length).
        return (this.size / this.table.length).toFixed(3);  // Return a fixed decimal representation of the load factor.
    }
    display() {  // Display the contents of the hash table.
        this.table.forEach((value, index) => {
            console.log(index, ':', (value.length > 1) ? value : value[0]);  // Output each index and its associated values.
        });
    }
    insert(key, value) {  // Insert a key-value pair into the hash table.
        const index = this._hash(key);  // Calculate the index for the key.
        if (this.table[index]) {  // If the index already contains data (collision handling).
            for (let i = 0; i < this.table[index].length; i++) {
                if (this.table[index][i][0] === key) {  // If the key already exists, update its value.
                    this.table[index][i][1] = value;
                    return;
                }
            }
            this.table[index].push([key, value]);  // If not, add a new key-value pair to the index.
        } else {
            this.table[index] = [];  // If the index is empty, create a new array.
            this.table[index].push([key, value]);  // Add the key-value pair to the new array.
        }
        this.size++;  // Increase the size of the hash table.
    }
    retrieve(key) {  // Retrieve a value by its key.
        const entry = this._hash(key);
        if (this.table[entry]) {  // If the index exists and contains data.
            for (let i = 0; i < this.table[entry].length; i++) {
                if (this.table[entry][i][0] === key) {  // Find and return the value associated with the key.
                    return this.table[entry][i][1];
                }
            }
        }
        return undefined;  // Return undefined if the key is not found.
    }
    delete(key) {  // Delete a key-value pair by key.
        const index = this._hash(key);
        if (this.table[index] && this.table[index].length) {  // If the index exists and is not empty.
            for (let i = 0; i < this.table[index].length; i++) {
                if (this.table[index][i][0] === key) {  // Find and remove the key-value pair.
                    this.table[index].splice(i, 1);
                    this.size--;  // Decrease the size of the hash table.
                    return true;  // Return true to indicate success.
                }
            }
        } else {
            return false;  // Return false to indicate that the key was not found.
        }
    }
}
const ht = new HashTable();  // Create an instance of the HashTable class.
ht.insert('Ford', 250);  // Insert key-value pairs.
ht.insert('Audi', 320);
ht.insert('Bugatti', 457);
ht.insert('U', 100);  // This will collide with 'Bugatti'.
ht.display();  // Display the contents of the hash table.
// Output:
// 6 :  [ 'Audi', 320 ]
// 14 : [ 'Ford', 250 ]
// 85 : [ [ 'Bugatti', 457 ], [ 'U', 100 ] ]
console.log(ht.loadFactor());  // Output the load factor (0.031).
console.log('\nretrieved: ', ht.retrieve('Ford'));  // Retrieve and print values by keys.
console.log('retrieved: ', ht.retrieve('Audi'));
console.log('retrieved: ', ht.retrieve('Bugatti'));
console.log('retrieved: ', ht.retrieve('U'));
console.log('\n' + ht.delete('U'));  // Delete a key-value pair and output true if successful.
ht.display();  // Display the updated contents of the hash table.
// Output:
// 6:  [ 'Audi', 320 ]
// 14: [ 'Ford', 250 ]
// 85: [ 'Bugatti', 457 ]

Graph Algorithm

Dijkstra’s shortest path algorithm

Dijkstra's shortest path algorithm is a method for determining the most efficient route between two nodes in a graph by considering the associated costs or weights on the edges. It's widely used in applications like GPS navigation, network routing, and logistics optimization.

function dijkstra(graph, source) {
  // Initialize the distance array.
  let distance = new Array(graph.length).fill(Infinity);
  distance[source] = 0;
  // Initialize the visited array.
  let visited = new Array(graph.length).fill(false);
  // Create a priority queue.
  let priorityQueue = new PriorityQueue();
  priorityQueue.add(source, 0);
  // While the priority queue is not empty:
  while (!priorityQueue.isEmpty()) {
    // Get the vertex with the minimum distance.
    let currentVertex = priorityQueue.remove();
    // Mark the vertex as visited.
    visited[currentVertex] = true;
    // For each neighbor of the current vertex:
    for (let neighbor of graph[currentVertex]) {
      // If the neighbor has not been visited:
      if (!visited[neighbor]) {
        // Calculate the new distance to the neighbor.
        let newDistance = distance[currentVertex] + graph[currentVertex][neighbor];
        // If the new distance is shorter than the current distance:
        if (newDistance < distance[neighbor]) {
          // Update the distance to the neighbor.
          distance[neighbor] = newDistance;
          // Add the neighbor to the priority queue.
          priorityQueue.add(neighbor, newDistance);
        }
      }
    }
  }
  // Return the distance array.
  return distance;
}

Conclusion

Wrapping up the initial segment of this three-part blog series, it's essential to understand that data structures serve as the fundamental pillars of efficient algorithms and problem-solving in the realm of computer science. Though they may seem intricate at first glance, with consistent practice and the proper guidance, you'll soon discover their prowess and be able to harness it for crafting elegant and efficient solutions.

Thank you for joining us in this exploration. I appreciate your readership. Be sure to stay tuned for the next two parts of this series, where we'll delve deeper into the fascinating world of data structures and algorithms. Happy coding!

Acknowledgements

Sites used for visualizations:

Visualgo - Visualgo website
Heap Visualization by Ben Frederickson - Heap Visualization by Ben Frederickson
Pathfinding Visualizer by Clement Mihailescu - Pathfinding Visualizer by Clement Mihailescu
CSVISTool - CSVISTool website
Algorithms Visualization by cs.usfca.edu - Algorithms Visualization by cs.usfca.edu

Discover Three.js: Intro and Study Guide

Cris — Wed, 18 Oct 2023 10:07:43 +0000

There are many ways to approach learning Three.js. You can start by reading the documentation, watching tutorials, or taking online courses. However, it can be challenging to find the right resources and know where to begin. This study guide provides a basic roadmap for beginners to start learning Three.js. It covers essential concepts, topics, and actionable steps for effective learning. Make sure to follow the provided resources for detailed explanations and practical examples.

What is Three.js?

It is a JavaScript library and API that works seamlessly across different web browsers. It's primarily used for creating and showcasing interactive 3D graphics using WebGL.

Three.js enables you to apply textures and materials to your objects. It also provides various light sources to illuminate your scene, advanced postprocessing effects, custom shaders, etc.

Here are some examples of what you can build with Three.js and its ecosystem:

Three.js Examples - Official examples from the Three.js repository.
Three.js Journey - A course by Bruno Simon that teaches you how to build 3D scenes using Three.js.
Three.js Official Website - The official website of Three.js.
ShaderToy - A site to showcase some of the best shaders.
Hadaka.jp - Company website that uses Three.js to create a 3D experience.
Elysium - A 3D experience that uses Three.js and WebGL.
Lost for You - A 3D experience that uses Three.js and WebGL.
Akella's YouTube Streams - A YouTube channel that showcases some of the best Three.js projects.

What is React Three Fiber?

Im sure that if you have some level of interest in Three.js you have heard about (R3F) React Three Fiber (or you will eventually) and you are wondering what is it and why would you use it. I will try to explain it in a simple way.

React-three-fiber, often referred to as R3F, It's a JavaScript library that builds on top of React and leverages the power of WebGL and Three.js. It's a powerful tool for both web and React Native development.

So, why should you consider React Three Fiber? It makes building dynamic 3D scenes much easier by allowing you to create declarative, reusable components. This approach brings clean and reactive coding practices to 3D graphics and opens up opportunities for integrating various packages for state management, animation, and gestures.

React Three Fiber acts as a bridge between React and Three.js, making it easy to build interactive 3D web applications without getting bogged down in Three.js's specifics. It remains compatible with different versions of Three.js, providing consistency in behavior.

If you're already familiar with React, you'll find it easy to get started with React Three Fiber. It's a great way to learn Three.js and WebGL while building interactive 3D scenes. and if you want to dive deeper into the world of 3D graphics, you can always use Three.js directly.
to learn a bit more about React Three Fiber, check out the following resources: React Three Fiber Documentation and I Wish I Knew This Before Using React Three Fiber

How to get started with Three.js?

With the basic info out of the way, let's get started with Three.js. The following sections provide a step-by-step guide for learning Three.js. It covers the essential concepts, topics, and actionable steps for effective learning. Make sure to follow the provided resources for detailed explanations and practical examples.

Key Concepts	Important Topics	Actionable Steps for Effective Learning
1. WebGL	WebGL rendering pipeline	- Familiarize yourself with the basics of WebGL and its rendering pipeline.
		- Learn about vertex and fragment shaders and how they contribute to the rendering process.
		- Understand how to create and manipulate WebGL contexts and buffers.
		- Practice rendering simple shapes using WebGL.
		- Resources:
		- WebGL Fundamentals
		- MDN WebGL tutorial
		- Awesome WebGL GitHub Repository
		- The Book of Shaders
2. Three.js	Basics of Three.js	- Learn the fundamental concepts of Three.js, such as scenes, cameras, and renderers.
		- Understand how to create and manipulate geometries, materials, and textures in Three.js.
		- Explore different types of lights and shadows in Three.js.
		- Practice creating and animating 3D objects using Three.js.
		- Resources:
		- Three.js Documentation
		- Awesome Three.js GitHub Repository
		- Discover Three.js
		- Three.js Fundamentals
3. Interaction	User input and controls	- Learn how to handle user interactions, such as mouse and keyboard events, in Three.js.
		- Explore different types of controls, such as OrbitControls and TrackballControls, for navigating and manipulating the scene.
		- Understand how to implement picking and raycasting for object selection and interaction.
		- Practice adding interactivity to your Three.js applications.
		- Resources:
		- Interactive 3D Graphics course (Note: Some parts may require WebGL knowledge)
4. Optimization	Performance and best	- Learn techniques for optimizing rendering performance in Three.js, such as efficient rendering, reducing draw calls, and implementing level of detail (LOD) techniques.
	practices	- Understand how to use shaders for advanced visual effects and performance improvements.
		- Explore tools like the Chrome DevTools for profiling and debugging Three.js applications.
		- Practice optimizing your Three.js projects for better performance.
		- Resources:
		- Optimizing WebGL Performance
		- Three.js Performance Tips

Note: This study guide is not meant to be exhaustive. It provides a basic roadmap for beginners to start learning Three.js. You can always explore other topics and resources to expand your knowledge.