CECS 528 Recordings of Lectures

• Thursday November 5th, 3SAT to Clique Mapping Reduction, 3SAT to Subset Sum Mapping Reduction
• Wednesday November 4th, 3SAT Decision Problem, SAT to 3SAT Mapping Reduction, 3SAT to Clique Mapping Reduction
• Tuesday November 3rd, Satisfiability Problem, NP-Completeness, Cook's Theorem, 3SAT
• Monday, November 2nd, Satisfiability Problem, NP-Completeness, Cook's Theorem
• Monday, October 26th, Complexity Theory and Class co-NP
• Thursday, October 21st, Class NP and Showing that a Decision Problem is in NP
• Wednesday, October 21st, Class NP and Showing that a Decision Problem is in NP
• Tuesday, October 20th, Complexity Theory and Class P
• Monday, October 19th, Complexity Theory and Class P
• Saturday, October 17th, Reducing Vertex Cover to Half Vertex Cover
• Thursday, October 15th, Mapping Reducibilities: HP to LPath, SS to SP, Vertex Covers
• Wednesday, October 14th, Mapping Reducibilities: HP to LPath, SS to SP, Vertex Covers
• Tuesday, October 13th, Mapping Reducibilities: Even to Odd, Clique to IS, SP to SS
• Monday, October 12th, Mapping Reducibilities: Even to Odd, Clique to IS, SP to SS
• Tuesday, October 6th
• Monday, October 5th
• Thursday, October 1st, Edit Distance Example and Optimal Binary Search Tree
• Wednesday, September 30th, Optimal Binary Search Tree Example, Single-Source Distances in DAGs
• Wednesday, September 30th, Edit Distance Example and Optimal Binary Search Tree
• Tuesday, September 29th, 0-1 Knapsack, Edit Distance
• Monday, September 28th, 0-1 Knapsack, Edit Distance
• Saturday, September 26th, Introduction to Approximation Algorithms
• Thursday, September 24th, Dijkstra's Algorithms with data structure support and Introduction to Dynamic Programming,
• Wednesday, September 23rd, Prim's and Dijkstra's Algorithms with data structure support,
• Tuesday, September 22nd, Minimum Spanning Trees, Kruskal's and Prim's Algorithms with data structure support,
• Monday, September 21st, Unit Task Scheduling, Minimum Spanning Trees, Kruskal's Algorithm, Applications of DS Data Structure
• Tuesday, September 15th, Disjoint Set Data Structure, Unit Task Scheduling, Graphs Review
• Monday, September 14th, Introduction to Greedy Algorithms, Binary Heaps, Disjoint Set Data Structure
• Thursday, September 10th, Introduction to Greedy Algorithms, Binary Heaps, Disjoint Set Data Structure
• Wednesday, September 9th, Finding Statistics, Strassen's Algorithm
• Tuesday, September 8th, Finding Statistics, Strassen's Algorithm
• Recurrences: Substitution Method Example 6
• Tuesday, September 3rd, Quicksort, Finding Array Statistics
• Wednesday, September 2nd, Quickort, Finding Array Statistics (Unfortunately, this did not get recorded
• Tuesday, September 1st, Substitution Method
• Monday, August 31st, Substitution Method
• Example 2 of Recurrences Lecture Demonstrating use of the Master Theorem
• Thursday, August 27th, Big-O Review, Recurrences
• Wednesday, August 26th, Mergesort, Master Theorem
• Tuesday, August 25th, Syllabus and Big-O Review