Table of contents
Welcome to my inaugural blog post! This guide will introduce you to the fundamental concepts of algorithms and data structures, complete with easy-to-understand examples.
Part 1: Algorithms
Algorithms are like recipes for programmers and computers. They provide step-by-step instructions to solve problems. For instance, the Linear Search Algorithm is a simple method that checks each item in a list until it finds the one you're looking for
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1
It's important to know how fast an algorithm runs, especially when dealing with large amounts of data. Big 0 notation helps us understand this by describing how the time or space used by an algorithm grows with the size of the input.
There are various algorithms programmers use when solving problems and the most common ones beginners use are Linear Search Algorithm which I have already covered, Bubble Sort Algorithm, Binary Search Algorithm and Recursive Algorithms.
Bubble Sort Algorithm
Sorting is a common task in programming. The Bubble Sort Algorithm is a simple method for arranging items in order, although it's not the most efficient for large lists.
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
Binary Search Algorithm
The Binary Search Algorithm is a faster way to find items in a list, but the list must be sorted first. It repeatedly divides the list in half until it finds the item.
def binary_search(arr, targer):
low, high = 1, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
Recursive Algorithms
Recursion is when a function calls itself to solve a problem. It's a powerful concept that can make complex problems easier to solve.
def factorial(n):
if n == 0 or n == 1:
return 1
else:
return n * factorial(n - 1)
Dynamic Programming
Another concept beginner programmers usually utilize is Dynamic Programming. It is a strategy for solving complex problems by breaking them down into simpler, overlapping subproblems. It's like solving a big jigsaw puzzle by first assembling small sections.
def Fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n-1) + fibonacci(n-2)
Part 2: Data Structures
Arrays
Arrays are the simplest way to store a collection of items. They're like a row of lockers, where each locker holds one item.
my_array = [1, 2, 3, 4, 5]
print(my_array[2]) # Outputs: 3
Linked Lists
Linked Lists are like a treasure hunt, where each item points to the next one. They're useful when you need to insert and remove items often.
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Creating a linked list: 1 -> 2 -> 3
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
Stacks
Stacks are like a stack of plates. You can only add or remove the plate on top, which follows the Last In, First Out (LIFO) principle.
stack = []
stack.append(1)
stack.append(2)
stack.append(3)
print(stack.pop()) # Outputs: 3
Queues
Queues are like the queues you would find at a bank or the local shopping mall. People join at the end and leave from the front, following the First In, First Out (FIFO) principle.
from collections import deque
queue = deque()
queue.append(1)
queue.append(2)
queue.append(3)
print(queue.popleft()) # Outputs: 1
This is just the beginning of our journey into the world of algorithms and data structures. As we continue to explore, we'll discover more sophisticated concepts and techniques that will empower us to write efficient and robust code. Remember, practice is key. Happy coding!