CS50 2024 | Algoritmos (Aula 3) - Curso de Introdução à Ciência da Computação de Harvard

Introduction

This tutorial will guide you through key concepts related to algorithms, including search methods, sorting techniques, and asymptotic notation. By the end, you'll have a better understanding of how algorithms work, how to measure their efficiency, and how to implement basic algorithms in code.

Step 1: Understanding Algorithms

• An algorithm is a process or set of rules to be followed in calculations or problem-solving operations.
• Think of it as a "black box" that takes input and produces output.
• It's essential to understand how an algorithm interacts with a problem to determine the time it takes to solve it.

Step 2: Exploring Search Algorithms

Linear Search

• Definition: A simple search algorithm that checks each element in a list until the desired element is found or the list ends.
• How it works:
  1. Start from the first element.
  2. Compare each element with the target.
  3. If a match is found, return the index; if not, return a failure indication.

Binary Search

• Definition: A more efficient search algorithm that works on sorted lists by repeatedly dividing the search interval in half.
• How it works:
  1. Start with the middle element of the sorted list.
  2. If the middle element equals the target, return its index.
  3. If the target is less than the middle element, search the left half.
  4. If the target is greater, search the right half.
  5. Repeat until the target is found or the interval is empty.

Step 3: Learning Sorting Algorithms

Bubble Sort

• Definition: A straightforward sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.
• How it works:
  1. Compare the first two elements.
  2. If the first is greater than the second, swap them.
  3. Move to the next pair and repeat until the end of the list.
  4. Repeat the entire process until no swaps are needed.

Selection Sort

• Definition: This algorithm divides the list into sorted and unsorted regions and repeatedly selects the smallest (or largest) element from the unsorted region to move it to the sorted region.
• How it works:
  1. Find the minimum element in the unsorted list.
  2. Swap it with the leftmost unsorted element.
  3. Move the boundary between sorted and unsorted regions one element to the right.
  4. Repeat until the entire list is sorted.

Merge Sort

• Definition: A divide-and-conquer algorithm that divides the unsorted list into smaller sublists, sorts them, and then merges them back together.
• How it works:
  1. Divide the list into two halves.
  2. Recursively sort each half.
  3. Merge the two sorted halves back together.

Step 4: Understanding Asymptotic Notation

• Big O Notation (O): Represents the upper bound of an algorithm's running time, indicating the worst-case scenario.
• Omega Notation (Ω): Represents the lower bound, indicating the best-case scenario.
• Theta Notation (Θ): Represents the exact bound, indicating both upper and lower bounds.

Step 5: Introduction to Recursion

• Definition: A method where a function calls itself in order to solve smaller instances of the same problem.
• Key Points:
  • Ensure there is a base case to stop the recursion.
  • Use recursion for problems that can be broken down into smaller, similar problems.

Conclusion

In this tutorial, we covered the fundamental concepts of algorithms, including search and sorting methods, as well as asymptotic notation and recursion. Understanding these concepts is crucial for analyzing the efficiency of algorithms and improving your problem-solving skills in computer science. Next, consider implementing these algorithms in code to solidify your understanding.