Algorithms-UCSanDiego

Course 1: Algorithmic Toolbox

• Week 1: Programming Challenges
  • 1. Sum of Two Digits
  • 2. Maximum Pairwise Product
• Week 2: Algorithmic Warm-up
  • 1. Fibonacci Number
  • 2. Last Digit of a Large Fibonacci Number
  • 3. Greatest Common Divisor
  • 4. Least Common Multiple
  • 5. Fibonacci Number Again
  • 6. Last Digit of the Sum of Fibonacci Numbers
  • 7. Last Digit of the Sum of Fibonacci Numbers Again
  • 8. Last Digit of the Sum of Squared Fibonacci Numbers
• Week 3: Greedy Algorithms
  • 1. Money Change
  • 2. Maximum Value of the Loot ( fractional knapsack )
  • 3. Car Fueling
  • 4. Maximum Advertising Revenue
  • 5. Collecting Signatures ( min points to cover segments )
  • 6. Maximum Number of Prizes
  • 7. Maximum Salary
• Week 4: Divide and Conquer
  • 1. Binary Search
  • 2. Majority Element
  • 3. Improving Quicksort
  • 4. Array Inversions
• Week 5: Dynamic Programming - Part 1
  • 1. Money Change Again
  • 2. Primitive Calculator
  • 3. Edit Distance
  • 4. Longest Common Subsequence
  • 5. Longest Common Subsequence of Three Sequences
• Week 6: Dynamic Programming - Part 2
  • 1. Maximum Amount of Gold
  • 2. Partitioning Souvenirs
  • 3. Maximum Value of an Arithmetic Expression

Course 2: Data Structures

• Week 1: Basic Data Structures
  • 1. Check Brackets
  • 2. Tree Height
  • 3. Packet Processing
  • 4. Stack Maximum Value
• Week 2: Priority Queues and Disjoint Sets
  • 1. Convert Array into Heap
  • 2. Parallel Processing
  • 3. Merge Tables
• Week 3: Hash Tables and Hash Functions
  • 1. Phone Book
  • 2. Hashing with Chains
  • 3. Find Pattern in Text
• Week 4: Binary Search Trees
  • 1. Binary Tree Traversals
  • 2. Is Binary Search Tree (unique values)
  • 3. Is Binary Search Tree (duplicate values)

Course 3: Algorithms on Graphs

• Week 1: Graph Decomposition
  • 1. Graph Representation
  • 2. Reachability
  • 3. Connected Components
• Week 2: Graph Decomposition (continued)
  • 1. Graph Representation
  • 2. Directed Acyclic Graphs
  • 3. Topological Sort
  • 4. Stronly Connected Components
• Week 3: Paths in Graphs
  • 1. Graph Representation
  • 2. Breadth First Search
  • 3. Bipartite Graph
• Week 4: Paths in Graphs (continued)
  • 1. Graph Representation
  • 2. Dijkstra
  • 3. Bellman-Ford (negative cycle detection)
• Week 5: Minimum Spanning Trees
  • 1. Graph Representation
  • 2. Kruskal MST (connecting points)
  • 3. K-Clustering

Course 4: Algorithms on Strings

• Week 1: From Genome Sequencing to Pattern Matching
  • 1. Trie
  • 2. Trie Pattern Matching
  • 3. Trie Pattern Matching (prefix allowed)
  • 4. Suffix Tree
• Week 2: Burrows-Wheeler Transform and Suffix Arrays
  • 1. Burrows-Wheeler Transform
  • 2. Inverse Burrows-Wheeler Transform
  • 3. Pattern Matching
  • 4. Suffix Array
• Week 3: Knuth–Morris–Pratt Algorithm
  • 1. Exact Pattern Matching
• Week 4: Constructing Suffix Arrays and Suffix Trees
  • 2. Construct Suffix Array
    • Counting sort (detailed pseudocode)
    • Counting Sort (modern C++)
    • Counting Sort (legacy C)
  • 3. Pattern Matching with Suffix Array
  • [4. Construct Suffix Tree from Suffix Array]

Course 5: Advanced Algorithms and Complexity

• Week 1: Flows in Networks
  • 1. Evacuating People
• Week 2: Linear Programming
• Week 3: NP-complete Problems
• Week 4: Coping with NP-completeness
• Week 5: Streaming Algorithms

Supplemental Resources

• Master-Theorem
• Algorithms: Dasgupta-Papadimitriou-Vazirani ( 2006 )
• Algorithms and Data Structures: Mehlhorn-Sanders ( 2007 )
• Introduction to Algorithms: Cormen-Leiserson-Rivest-Stein ( 2009 )
• Introduction to Algorithms: A Creative Approach ( 2019 )
• Discrete Probability
• Mathematical Proofs