-
From CS Largeclass
62 plays 0- 3SAT to hamiltonian cycle - 3SAT to graph coloring - 3SAT to CSAT (and reverse too!) -
From CS Largeclass
89 plays 0- Cook-Levin Theorem - Reduction: 3SAT -> Subset-sum -
From CS Largeclass
132 plays 0-Sample reduction from SAT to independent set -Re-review of complexity classes -P/NP comparison to DFA/NFA -Introduction to certificate and certificate jargon -
From CS Largeclass
181 plays 0Basic conceptual overview of reductions Independent Sets / Cliques Intro to SAT -
From CS Largeclass
153 plays 0- Minimum Spanning Trees - Proof of MST algorithms via safe edges -
From Andrew Miller
150 plays 0Greedy algorithms and exchange proofs of optimality - Interval scheduling - Minimum max-lateness -
From Andrew Miller
126 plays 0- Bellman Ford shortest paths -
From CS Largeclass
136 plays 0- Breadth first search - Dijkstra's shortest paths algorithm -
From CS Largeclass
141 plays 0Linear time algorithm for finding SCCs of G and meta-graph of SCCs. -
From Nickvash Kani
183 plays 0- Topological Sorting - Depth First Search with Pre-/Post numbering -
From Andrew Miller
133 plays 0- Code example of Optimal Binary Search Tree example - Parsing and the CYK algorithm -
From Andrew Miller
196 plays 0- Long increasing subsequence recap - Edit distance - Optimal Binary Search Tree -
From Andrew Miller
219 plays 0- Dynamic programming - Improving solution to SubsetSum - A look at the rubrics and step by step guide to dynamic programming solutions -
From Andrew Miller
170 plays 0- Brute force strategies - Backtracking strategies - 8 queens, subset sum - Memoization & fibonacci -
From Nickvash Kani
59 plays 0Quick Select explained more. -
From Andrew Miller
153 plays 0- Karatsuba - Median of Medians and Quickselect -
From Andrew Miller
226 plays 0- Recursion / reduction - Towers of Hanoi - Merge sort -
From CS Largeclass
152 plays 0Examples of Turing reductions, recurrence expressions, and context-free grammar -
From Andrew Miller
171 plays 0- Cantor's diagonalization argument - Undecidability and halting problem -
From Andrew Miller
169 plays 0- CFG closure properties - Turing Machines - PDAs -
From Andrew Miller
195 plays 0- Context Free Grammars, parse trees -
From Andrew Miller
198 plays 0- Proving languages non-regular with fooling sets - Proving languages non-regular with Closure Properties - A bit about the Myhill-Nerode theorems -
From Andrew Miller
160 plays 0- Finish DFAs and product construction - NFAs -
From Andrew Miller
202 plays 0- Closure properties of NFA - DFA<->NFA<->Regular equivalence -
From Andrew Miller
246 plays 0Finish up regexes A coding example using regexp library! Start talking about DFAs -
From Andrew Miller
331 plays 0Reviewing strings Some inductive proofs Facts about languages and a first result in computability theory Introducing regular languages / expressions -
From Andrew Miller
400 plays 0Introduction to class! Administrative stuff Starting to discuss strings
Search for ""
Public, Restricted and Moderated
- Managers: