CSCE 411H Design and Analysis of Algorithms

Spring 2016
Course Information


Where: HRBB 126
When: MW 4:10pm-5:25pm

Instructor: Andreas Klappenecker
Office: HRBB, Room 509B
Office Hours: MT 1:30-2:30pm or by appointment.
e-mail: klappi at cse.tamu.edu

Teaching Assistant: Pulakesh Upadhyaya
Office: HRBB 526
Office hours: MW 2:00-4:00pm, F 10:00am-noon.

General Information


Course information: The syllabus can be found on howdy.
Questions? Come to our office hours or ask during class.

Announcements

Homework

Schedule

W Jan 20 Introduction; read Chapters 1-2 for background
M Jan 25 Asymptotic notation; read lectures notes Ch. 9; CLRS Ch. 3
W Jan 27 Sums; read lecture notes Ch. 7
M Feb 01Lower bounds
T Feb 02 Flipped: Finding the 2nd Largest Element
W Feb 03Lower bounds
M Feb 08 Review: Divide and Conquer (optional)
M Feb 08 Review: Strassen's matrix multiplication (optional)
M Feb 08 Divide and Conquer; read Chapter 4
T Feb 09 Flipped: Fast Fourier Transform, Part I
T Feb 09 Flipped: Fast Fourier Transform, Part II
W Feb 10 Divide and Conquer; Fast Fourier Transform
M Feb 15 Review: Greedy Algorithms: Giving Change (review)
M Feb 15 Greedy Algorithms; read Chapter 16
W Feb 16 Greedy Algorithms and Matroids; read Chapter 16
W Feb 16 Review: Greedy Algorithms and Matroids
M Feb 22 Greedy Algorithms; Dynamic Programming; read Chapter 15
T Feb 23 Flipped: Bipartite Matching
W Feb 24 Dynamic Programming; read Chapter 15
R Feb 25 Flipped: Matrix Chain video
S Feb 27 Review: Amortized Analysis of the Multipop Stack
M Feb 29 Amortized Analysis; read Chapter 17
W Mar 02 Midterm
M Mar 07 Midterm solution; Amortized Analysis; Graph Algorithms
T Mar 08 Review: Amortized Analysis of vector::push_back
W Mar 09 Topological Sorting, Strongly Connected Components, Quiz
M Mar 14 Spring break
W Mar 16 Spring break
M Mar 21 Shortest Path Algorithms
W Mar 23 Randomized Algorithms, background; Quiz
W Mar 23 Flipped: Background on Probability Theory
M Mar 28 Randomized algorithms; minimum cut
W Mar 30 Randomized Algorithms; Randomized Quicksort and Selection
M Apr 04 Birthday problems
W Apr 06 2SAT, Complexity Theory
M Apr 11 Complexity Theory: The Complexity Classes P and NP
W Apr 13 Complexity Theory: NP-Completeness, SAT, 3SAT
R Apr 14 Flipped: Read Chapter 34 in CLRS
M Apr 18 Complexity Theory
W Apr 20 Complexity Theory
M Apr 25 Undecidability
W Apr 27 Undecidability, Complexity Potpurri, Quiz
M May 02 Review

Lecture Notes and Slides

All classmaterial is copyrighted. Reposting is not permitted.