TIL: MIT OpenCourseWare - Algorithms and Computer Science Fundamentals

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

# Binary Search Tree Implementation
class BSTNode:
    def __init__(self, key, value=None):
        self.key = key
        self.value = value
        self.left = None
        self.right = None
        self.parent = None

class BinarySearchTree:
    def __init__(self):
        self.root = None
    
    def insert(self, key, value=None):
        """Insert key-value pair into BST"""
        if not self.root:
            self.root = BSTNode(key, value)
            return
        
        current = self.root
        while True:
            if key < current.key:
                if current.left is None:
                    current.left = BSTNode(key, value)
                    current.left.parent = current
                    break
                current = current.left
            elif key > current.key:
                if current.right is None:
                    current.right = BSTNode(key, value)
                    current.right.parent = current
                    break
                current = current.right
            else:
                current.value = value  # Update existing key
                break
    
    def search(self, key):
        """Search for key in BST - O(log n) average case"""
        current = self.root
        while current:
            if key == current.key:
                return current.value
            elif key < current.key:
                current = current.left
            else:
                current = current.right
        return None
    
    def delete(self, key):
        """Delete node with given key"""
        node = self._find_node(key)
        if not node:
            return False
        
        # Case 1: No children (leaf node)
        if not node.left and not node.right:
            if node.parent:
                if node.parent.left == node:
                    node.parent.left = None
                else:
                    node.parent.right = None
            else:
                self.root = None
        
        # Case 2: One child
        elif not node.left or not node.right:
            child = node.left if node.left else node.right
            if node.parent:
                if node.parent.left == node:
                    node.parent.left = child
                else:
                    node.parent.right = child
                child.parent = node.parent
            else:
                self.root = child
                child.parent = None
        
        # Case 3: Two children - replace with successor
        else:
            successor = self._find_min(node.right)
            node.key = successor.key
            node.value = successor.value
            self._delete_node(successor)
        
        return True

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

# Classic DP Examples from MIT 6.006

def fibonacci_dp(n):
    """Fibonacci using dynamic programming - O(n) time, O(n) space"""
    if n <= 1:
        return n
    
    dp = [0] * (n + 1)
    dp[1] = 1
    
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    
    return dp[n]

def longest_common_subsequence(text1, text2):
    """LCS using 2D DP - O(mn) time and space"""
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    return dp[m][n]

def coin_change(coins, amount):
    """Minimum coins to make amount - classic DP problem"""
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], dp[i - coin] + 1)
    
    return dp[amount] if dp[amount] != float('inf') else -1

# Example usage
print(f"Fibonacci(10): {fibonacci_dp(10)}")
print(f"LCS('ABCDGH', 'AEDFHR'): {longest_common_subsequence('ABCDGH', 'AEDFHR')}")
print(f"Coin change for 11 with [1,2,5]: {coin_change([1,2,5], 11)}")

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

# Mathematical induction examples from the course

def prove_sum_formula(n):
    """
    Prove: Sum of first n natural numbers = n(n+1)/2
    Using mathematical induction
    """
    # Base case: n = 1
    if n == 1:
        left_side = 1
        right_side = 1 * (1 + 1) // 2
        assert left_side == right_side, f"Base case failed: {left_side} != {right_side}"
        return True
    
    # Inductive step: Assume true for k, prove for k+1
    # If sum(1 to k) = k(k+1)/2, then sum(1 to k+1) = (k+1)(k+2)/2
    k = n - 1
    sum_to_k = sum(range(1, k + 1))
    expected_sum_to_k = k * (k + 1) // 2
    
    sum_to_n = sum_to_k + n
    expected_sum_to_n = n * (n + 1) // 2
    
    return sum_to_n == expected_sum_to_n

def fibonacci_closed_form(n):
    """
    Fibonacci closed form using golden ratio
    Demonstrates mathematical analysis of recursive relations
    """
    import math
    
    phi = (1 + math.sqrt(5)) / 2  # Golden ratio
    psi = (1 - math.sqrt(5)) / 2  # Conjugate
    
    # Binet's formula
    fib_n = (phi**n - psi**n) / math.sqrt(5)
    return round(fib_n)

# Graph theory applications
class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.adj_list = {i: [] for i in range(vertices)}
    
    def add_edge(self, u, v):
        self.adj_list[u].append(v)
        self.adj_list[v].append(u)  # Undirected graph
    
    def is_bipartite(self):
        """
        Check if graph is bipartite using 2-coloring
        Demonstrates proof by contradiction
        """
        color = [-1] * self.V
        
        def dfs_color(node, c):
            color[node] = c
            for neighbor in self.adj_list[node]:
                if color[neighbor] == -1:
                    if not dfs_color(neighbor, 1 - c):
                        return False
                elif color[neighbor] == color[node]:
                    return False  # Contradiction found
            return True
        
        for i in range(self.V):
            if color[i] == -1:
                if not dfs_color(i, 0):
                    return False
        return True

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

import math
from fractions import Fraction

def combinations(n, k):
    """Calculate C(n,k) = n! / (k!(n-k)!)"""
    if k > n - k:  # Optimization: C(n,k) = C(n,n-k)
        k = n - k
    
    result = 1
    for i in range(k):
        result = result * (n - i) // (i + 1)
    return result

def binomial_probability(n, k, p):
    """
    Binomial probability: P(X = k) = C(n,k) * p^k * (1-p)^(n-k)
    """
    return combinations(n, k) * (p ** k) * ((1 - p) ** (n - k))

def expected_value_dice():
    """Calculate expected value of fair six-sided die"""
    outcomes = list(range(1, 7))
    probability = Fraction(1, 6)
    
    expected = sum(outcome * probability for outcome in outcomes)
    return expected

def birthday_paradox(n):
    """
    Calculate probability that n people have at least one shared birthday
    Classic probability problem demonstrating counterintuitive results
    """
    if n > 365:
        return 1.0
    
    # Calculate probability that all have different birthdays
    prob_all_different = 1.0
    for i in range(n):
        prob_all_different *= (365 - i) / 365
    
    # Probability of at least one match
    return 1 - prob_all_different

# Example calculations
print(f"C(10,3) = {combinations(10, 3)}")
print(f"Expected die value: {expected_value_dice()}")
print(f"Birthday paradox for 23 people: {birthday_paradox(23):.3f}")

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

# Algorithm design considering hardware characteristics

def cache_friendly_matrix_multiply(A, B):
    """
    Matrix multiplication optimized for cache locality
    Uses blocking to improve cache performance
    """
    n = len(A)
    C = [[0] * n for _ in range(n)]
    block_size = 64  # Typical cache line size consideration
    
    for i in range(0, n, block_size):
        for j in range(0, n, block_size):
            for k in range(0, n, block_size):
                # Process block
                for ii in range(i, min(i + block_size, n)):
                    for jj in range(j, min(j + block_size, n)):
                        for kk in range(k, min(k + block_size, n)):
                            C[ii][jj] += A[ii][kk] * B[kk][jj]
    return C

def parallel_merge_sort(arr):
    """
    Merge sort designed for parallel execution
    Demonstrates divide-and-conquer parallelization
    """
    import concurrent.futures
    
    def merge(left, right):
        result = []
        i, j = 0, 0
        
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                result.append(left[i])
                i += 1
            else:
                result.append(right[j])
                j += 1
        
        result.extend(left[i:])
        result.extend(right[j:])
        return result
    
    def merge_sort_parallel(arr, depth=0):
        if len(arr) <= 1:
            return arr
        
        mid = len(arr) // 2
        
        # Use parallelization for larger subarrays
        if len(arr) > 1000 and depth < 3:
            with concurrent.futures.ThreadPoolExecutor() as executor:
                left_future = executor.submit(merge_sort_parallel, arr[:mid], depth + 1)
                right_future = executor.submit(merge_sort_parallel, arr[mid:], depth + 1)
                
                left = left_future.result()
                right = right_future.result()
        else:
            left = merge_sort_parallel(arr[:mid], depth + 1)
            right = merge_sort_parallel(arr[mid:], depth + 1)
        
        return merge(left, right)
    
    return merge_sort_parallel(arr)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

import time
import matplotlib.pyplot as plt
import numpy as np

class AlgorithmAnalyzer:
    """Framework for empirical algorithm analysis"""
    
    def __init__(self):
        self.results = {}
    
    def time_algorithm(self, algorithm, inputs, name="Algorithm"):
        """Time algorithm execution across different input sizes"""
        times = []
        sizes = []
        
        for input_data in inputs:
            size = len(input_data) if hasattr(input_data, '__len__') else input_data
            
            start_time = time.perf_counter()
            algorithm(input_data)
            end_time = time.perf_counter()
            
            times.append(end_time - start_time)
            sizes.append(size)
        
        self.results[name] = {'sizes': sizes, 'times': times}
        return sizes, times
    
    def compare_algorithms(self, algorithms, input_generator):
        """Compare multiple algorithms on same inputs"""
        test_inputs = [input_generator(size) for size in [100, 500, 1000, 2000, 5000]]
        
        for name, algorithm in algorithms.items():
            self.time_algorithm(algorithm, test_inputs, name)
    
    def plot_results(self):
        """Plot timing results for visual comparison"""
        plt.figure(figsize=(10, 6))
        
        for name, data in self.results.items():
            plt.plot(data['sizes'], data['times'], marker='o', label=name)
        
        plt.xlabel('Input Size')
        plt.ylabel('Execution Time (seconds)')
        plt.title('Algorithm Performance Comparison')
        plt.legend()
        plt.grid(True)
        plt.show()

# Example usage
def bubble_sort(arr):
    arr = arr.copy()
    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]
    return arr

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)

# Analyze sorting algorithms
analyzer = AlgorithmAnalyzer()
algorithms = {
    'Bubble Sort': bubble_sort,
    'Quick Sort': quick_sort,
    'Python Built-in': sorted
}

def generate_random_array(size):
    return np.random.randint(0, 1000, size).tolist()

analyzer.compare_algorithms(algorithms, generate_random_array)
# analyzer.plot_results()  # Uncomment to see visualization

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

# Structured approach to MIT OpenCourseWare study
class MITCourseStudyPlan:
    def __init__(self, course_name):
        self.course_name = course_name
        self.completed_lectures = set()
        self.problem_sets = {}
        self.projects = {}
    
    def track_lecture(self, lecture_number, notes=""):
        """Track completed lectures with notes"""
        self.completed_lectures.add(lecture_number)
        print(f"Completed Lecture {lecture_number}: {notes}")
    
    def add_problem_set(self, ps_number, problems_solved, total_problems):
        """Track problem set progress"""
        self.problem_sets[ps_number] = {
            'solved': problems_solved,
            'total': total_problems,
            'completion': problems_solved / total_problems
        }
    
    def progress_report(self):
        """Generate study progress report"""
        total_lectures = len(self.completed_lectures)
        ps_avg = sum(ps['completion'] for ps in self.problem_sets.values()) / len(self.problem_sets) if self.problem_sets else 0
        
        return {
            'course': self.course_name,
            'lectures_completed': total_lectures,
            'problem_set_average': ps_avg,
            'overall_progress': (total_lectures * 0.6 + ps_avg * 0.4)  # Weighted score
        }

# Example usage
algorithms_course = MITCourseStudyPlan("6.006 Introduction to Algorithms")
algorithms_course.track_lecture(1, "Asymptotic Notation and Peak Finding")
algorithms_course.track_lecture(2, "Models of Computation and Binary Search Trees")
algorithms_course.add_problem_set(1, 8, 10)

math_course = MITCourseStudyPlan("6.042J Mathematics for Computer Science")
math_course.track_lecture(1, "Introduction and Proofs")
math_course.add_problem_set(1, 7, 8)

print("Progress Reports:")
print(algorithms_course.progress_report())
print(math_course.progress_report())