CSCE 411 Design and Analysis of Algorithms

• CSCE 411-501, 11:10am-12:25pm, HRBB 113

General Information

• You can find the syllabus on howdy.
• You can check your grades on ecampus

Announcements

• All flipped material is homework. Watch the videos before the next class period.
• Quizzes will be usually unannounced. They will often cover flipped material,concepts discussed in class, and reading assignments.
• Check e-campus for announcements, discussions, questions and answers.
• Sample Midterm
• Sample Final

Homework

• hw1.tex hw1.pdf
• hw2.tex hw2.pdf
• hw3.tex hw3.pdf
• hw4.tex hw4.pdf
• hw5.tex hw5.pdf (Updated)
• hw6.tex hw6.pdf
• hw7.tex hw7.pdf
• hw8.tex hw8.pdf (deadline extended to November 27).

Schedule

T Aug 28	Introduction, skim [CLRS] Chap 2, read Appendix A
R Aug 30	Asymptotic Notations, read Chapter 10 on perusall.com
T Sep 04	Asymptotic Notations, Lower Bounds, read Chapters 3 and 8.1 in [CLRS]
R Sep 06	Lower Bounds, read Chapter 9 in [CLRS]
T Sep 11	Lower Bounds, Divide and Conquer, read Chapter 4 in [CLRS]
R Sep 13	Divide and Conquer, Quiz on Asymptotic Notation and Lower Bounds,
T Sep 18	Divide and Conquer, Fast Fourier Transform, read Chapter 30 in [CLRS]
R Sep 20	Divide and Conquer, Fast Fourier Transform, Quiz on Divide and Conquer
T Sep 25	Greedy Algorithms, read Chapter 16 in [CLRS]
R Sep 27	Greedy Algorithms, Matroids, read Chapter 16 in [CLRS]
T Oct 02	Dynamic Programming, read Chapter 15 in [CLRS]
R Oct 04	Dynamic Programming, Quiz on Divide and Conquer, and Greedy
T Oct 09	Amortized Analysis, Review, read Chapter 17 in [CLRS]
R Oct 11	Midterm Exam
T Oct 16	Graph Algorithms
R Oct 18	Graph Algorithms DFS
T Oct 23	Graph Algorithms
R Oct 25	Randomized Algorithms
T Oct 30	Randomized Algorithms
R Nov 01	Randomized Algorithms
T Nov 06	Randomized Algorithms, Quiz
R Nov 08	Randomized Algorithms, Quiz
T Nov 13	2SAT, Complexity Theory
R Nov 15	Complexity Theory
T Nov 20	Complexity Theory, Quiz
R Nov 22	No classes
T Nov 27	Complexity Theory, Approximation Algorithms
R Nov 29	Approximation Algorithms, Undecidability, Quiz
T Dec 04	Undecidability, Review

Lecture Notes and Slides

• Introduction
• Asymptotic 1, Asymptotic 2, Asymptotic 3, Asymptotic 4
• Lower Bounds 1, Lower Bounds 2, Lower Bounds 3
• Divide and Conquer 1, Divide and Conquer 2, Divide and Conquer 3, Divide and Conquer 4
• Greedy Algorithms 1, Greedy Algorithms 2, Greedy Algorithms 3
• Dynamic Programming 1, Dynamic Programming 2, Dynamic Programming 3
• Amortized Analysis 1, Amortized Analysis 2, Amortized Analysis 3, Amortized Analysis 4
• Graph Algorithms 1, Graph Algorithms 2, Graph Algorithms 3, Graph Algorithms 4, Graph Algorithms 5, Graph Algorithms 6
• Randomized Algorithms 1, Randomized Algorithms 2, Randomized Algorithms 3, Randomized Algorithms 4, Randomized Algorithms 5,
  Probabilistic Biquorums, 2SAT. Background: Probability Theory, Random Variables, Repetitions.
• Complexity 1, Complexity 2, Complexity 3, Complexity 4, Complexity 5, Complexity 6, Complexity 7
• Undecidability
• Review