Algorithms and Data Structures Lecture

Introduction

• Presented by Passan at Treehouse via FreeCodeCamp
• Aim: Dispel fear/perceived inaccessibility of algorithms
• Focus: Core concepts, not specific algorithms
• Language: Python
• Requirement: Basic programming knowledge

What is an Algorithm?

• A set of steps to accomplish a task
• Examples: Recipes, Morning routines, Driving directions
• In programming: Steps a program takes to complete a task
• Algorithms exist to solve common CS problems efficiently

Key Concepts

• Importance: Avoid reinventing the wheel with inefficient solutions
• Algorithmic thinking: Breaking problems into distinct steps
• Compare and evaluate algorithms for best use case

Teaching Strategy

• Intersection of theoretical and practical approaches
• Practical coding examples using Python

Game to Illustrate Concepts

• Number guessing game:
  • Two players guess a number between 1 and 10.
  • Different strategies: Sequential guessing, Binary guessing
  • Purpose: Show different approaches/efficiencies in problem-solving

Algorithm Definition

• Need: Clearly defined input and output
• Steps: Specific, unbreakable, complete in finite time

Performance Measurement

• Time Complexity
• Space Complexity
• Running Time: Worst-case scenarios are critical for assessment

Common Time Complexities

• Constant time: O(1)
• Logarithmic time: O(log n)
• Linear time: O(n)
• Quadratic time: O(n²)
• Cubic time: O(n³)
• Quasi-linear: O(n log n)
• Exponential: O(2^n)
• Factorial: O(n!)

Python Coding Demos

Linear Search Algorithm

# Linear Search Implementation

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return None

Binary Search Algorithm

# Binary Search Implementation

def binary_search(arr, target):
    low = 0
    high = 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 None

Recursive Functions

# Recursive Sum Function

def recursive_sum(arr):
    if not arr:
        return 0
    return arr[0] + recursive_sum(arr[1:])

Merge Sort Algorithm

# Merge Sort Implementation

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    sorted_arr = []
    while left and right:
        if left[0] < right[0]:
            sorted_arr.append(left.pop(0))
        else:
            sorted_arr.append(right.pop(0))
    sorted_arr.extend(left or right)
    return sorted_arr

Quick Sort Algorithm

# Quick Sort Implementation

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

Data Structures

Linked List Implementation

Node Class

# Node class for linked list
class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None

    def __repr__(self):
        return f"Node({self.data})"

Linked List Class

# Linked list class
class LinkedList:
    def __init__(self):
        self.head = None

    def is_empty(self):
        return self.head is None

    def size(self):
        current = self.head
        count = 0
        while current:
            count += 1
            current = current.next
        return count

    def add(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def search(self, key):
        current = self.head
        while current and current.data != key:
            current = current.next
        return current

    def remove(self, key):
        current = self.head
        previous = None
        found = False
        while current and not found:
            if current.data == key:
                found = True
            else:
                previous = current
                current = current.next
        if current is None:
            return None
        if previous is None:
            self.head = current.next
        else:
            previous.next = current.next
        return current

Big O Notation Summary

• Linear Search: O(n)
• Binary Search: O(log n)
• Selection Sort: O(n²)
• Merge Sort: O(n log n)
• Quick Sort: Best-case O(n log n), Worst-case O(n²) depending on pivot choice

Conclusion

• Use appropriate data structures and algorithms based on the specific task and performance requirements.
• Focuses on developing algorithmic thinking: breaking down and solving problems step-by-step.
• Understanding Big O notation is crucial for performance analysis.