Documents for CSE 830

CSE 830: Design & Theory of Algorithms

Below are the documents and links needed for Fall 2020.

Syllabus - provides basic information about the course including how you will be graded.

Slack Discussion Board a place for asynchronous discussions and Q&A sessions.

Zoom will be used for all class sessions. The Zoom link has been e-mailed to all students and can be found pinned to the #general channel in the course Slack.

Below are the week-by-week topics that will be covered. Links will be added at least 24 hours before the first class each week (and often sooner). The current week will be in bold in the directory on the left of this page.

Week 1: Course Introduction

• Course Introduction (19:11)
• Why Study Algorithms? (18:29)
• Optional: Lightcycle Example Problem (7:39)
• Optional: Instructor Bio (9:14)

Week 2: Analytical Frameworks

• Using the RAM Model (17:51)
• Divide and Conquer (10:14)
• Asymptotic Notation (18:36)

• Graphing Code Results (11:30)

• Optional: “Live” Coding: Insertion Sort Algorithm (54:54)

• Optional: “Live” Coding: Other Sorting Algorithms (53:08)

• Proving Asymptotic Bounds on Insertion Sort (7:21)
• Proving Asymptotic Bounds on Mergesort (18:09)
• Recurrance Relations (16:21)

Week 3: Data Structures

• Introduction to Data Structures + Array and Lists (24:14)
• Binary Search Trees (6:10), by Dr. Emily Dolson

• Self-Balancing Binary Search Trees (11:11), by Dr. Emily Dolson

• Hash Tables (6:52), by Dr. Emily Dolson
• Binary Heaps (20:14)

Week 4: Algorithmic Thinking

• Order of Magnitude Problems (13:18)

• Algoritmic Thinking - Scale Problem 1 (8:27)
• Algoritmic Thinking - Scale Problem 2 (11:30)
• Algoritmic Thinking - Hat Problem 1 (7:26)
• Algoritmic Thinking - Hat Problem 2 (7:33)
• Algoritmic Thinking - Hat Problem 3 (11:36)

Week 5: Fundamental Algorithms 1

• Why Learn about Sorting Algorithms? (7:21)
• A Bestiary of Sorting Algorithms (19:42)
• Limits to Comparison-Based Sorting (10:27)
• Non-Comparison-Based Sorting (8:42)

• Which Sorting Algorithm Should You Use? (8:05)

• Introduction to Optimization Problems and Greedy Algorithms (7:53)
• Proofs of Algorithm Correctness (8:16)

Week 6: Fundamental Algorithms 2

• Randomness in Algorithms (10:09)
• Sources of Randomness (7:47)

• Random Number Generators (12:43)

• Algorithm Domains (12:27)
• Bloom Filters (15:37)

Week 7: Efficient Code 1

• Bit Representations (21:38)
• Counting Bits (6:14)
• Better Bit Counting (19:06)
• Magical Bit Counting (8:31)
• Bit Counting with Index Magic (6:34)

• Other Bit Tricks (9:19)

• Introduction to Python-specific Optimizations (4:15)
• Python Namespaces (14:10)
• Useful Python Features Tour (12:29)
• Generators in Python (7:09)

Week 8: Efficient Code 2

• Bits in C++ (21:15)

• Compile-Time Optimizations in C++ (14:05)

• Temporary Values in C++ (15:03)

• Other C++ Optimizations (23:57)

• Optional: Profiling Python Code (15:29)
• Optional: Profiling C++ Code (5:50)

Week 9: Recursive Techniques

• 5 Simple Steps for Solving Any Recusive Problem (21:02)

• Introduction to Dynamic Programming (11:14)
• When to use Dynamic Programming (16:01)

Week 10: Dealing with Hard Problems

• Calculating edit distance with dynamic programming (18:23)

• Brute-Force Chess Algorithm (14:46)

• Brute-Force Knapsack Algorithm (14:16)

• Bin Packing Optimization: Memory Management (22:06)
• Bin Packing Optimization: Caching small results (30:53)

Week 11: Graph Algorithms 1

• Introduction to Graph-Theory Terminology (12:52)

• Graph Traversal (18:40)
• Topological Sorting (9:27)
• Finding Articulation Verticies (9:56)

Week 12: Graph Algorithms 2

• Minimum Spanning Trees (9:07)
• Dijkstra’s Algorithm - Shortest Paths (4:10)

• PageRank (7:40)

• Brute Force Graph Algorithm Example (21:05)

Week 13: Inexact Optimization

• Heuristics (14:19)
• Approximation Algorithms (12:47)

Note: No class session on 11/26 (Thanksgiving)

Week 14: NP Completeness 1

• P, NP, and NP-Complete Problems (14:41)

• Proving NP Completeness (19:57)
• Proving that Integer Programming is NP-Complete (9:02)

Week 15: NP Completeness 2

• NP-Completeness Proof for Independent Set (17:59)

• More NP-Completeness Proofs (17:58)

• NP-Completeness Proof for Hamiltonian Cycle (and Traveling Salesman) (15:29)
• The Cook-Levin Theorem for Proving SAT is the Hardest Problem in NP (14:17 - across 6 short videos)

Finals Week: Review of Design Techniques / Special Topics

Week of 12/14

Pre-class videos: An overview of Design Techniques; Algorithms for Alternative Models of Computation; Other topics?

In class: Discussion about algorithms, course, and future changes.