CSCE 411 Design and Analysis of Algorithms

• CSCE 411-200 (honors): MWF 10:20am-11:10am, HRBB 126
• CSCE 411-501 (regular): MWF 11:30am-12:20pm, HRBB 113

General Information

• You can find the syllabus on howdy.
• You can check your grades on ecampus
• Final exam: CSCE 411-200 (honors) Monday, 5/8/2017, 8:00am-10:00am, in our classroom
• Final exam: CSCE 411-501 (regular) Tuesday, 5/9/2017, 10:30am-12:30pm, in our classroom

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

Homework

• hw1.tex hw1.pdf
• hw2.tex hw2.pdf
• hw3.tex hw3.pdf
• hw4.tex hw4.pdf
• hw5.tex hw5.pdf
• hw6.tex hw6.pdf
• hw7.tex hw7.pdf (update: clarified Problem 5)
• hw8.tex hw8.pdf
• hw9.tex hw9.pdf (updated)
• hw10.tex hw10.pdf (deadline extended until Wednesday, April 19)

Schedule

W Jan 18	Introduction, skim [CLRS] Chap 2, read Appendix A
F Jan 20	Asymptotic Analysis, read lecture notes on perusall
M Jan 23	Asymptotic Analysis, read lecture notes on perusall
T Jan 24	LaTeX (short intro, optional)
W Jan 25	Lower Bounds, Quiz, read Chapter 8 and slides
F Jan 27	Lower Bounds
M Jan 30	Divide and Conquer, read Chapter 4
W Feb 01	Divide and Conquer
F Feb 03	Homework 1, Divide and Conquer (FFT), read Chapter 30
S Feb 04	Flipped: Fast Fourier Transform, Part I
S Feb 04	Flipped: Fast Fourier Transform, Part II
M Feb 06	Divide and Conquer, FFT
W Feb 08	Divide and Conquer, FFT, Greedy Algorithms, read Chapter 16
F Feb 10	Greedy Algorithms, Quiz on Divide and Conquer
M Feb 13	Greedy Algorithms
W Feb 15	Greedy Algorithms, Dynamic Programming, read Chapters 15
F Feb 17	Dynamic Programming, Quiz on Greedy Algs. and Matroids
M Feb 20	Amortized Analysis
W Feb 22	Amortized Analysis, read Chapter 17
F Feb 24	Review
M Feb 27	Review, Quiz on Amortized Analysis
W Mar 01	Midterm Exam
F Mar 03	Midterm solutions
M Mar 06	Graph Algorithms
W Mar 08	Graph Algorithms, Quiz about Graphs
F Mar 10	Graph Algorithms
M Mar 13	Spring Break
W Mar 15	Spring Break
F Mar 17	Spring Break
M Mar 20	Randomized Algorithms
W Mar 22	Randomized Algorithms
F Mar 24	Randomized Algorithms
M Mar 27	Randomized Algorithms
W Mar 29	Randomized Algorithms, Birthday Paradox
F Mar 31	Randomized Algorithms, P vs NP, Quiz
M Apr 03	P vs NP
W Apr 05	NP Completeness
F Apr 07	NP Completeness, Quiz
M Apr 10	NP Completeness
W Apr 12	NP Completeness
F Apr 14	No classes
M Apr 17	NP Completeness, Approximation Algorithms
W Apr 19	Approximation Algorithms
F Apr 21	Undecidability
M Apr 24	Undecidability
W Apr 26	Undecidability
F Apr 28	Algorithmic Problems, Quiz on Undecidability
M May 01	Algorithmic Problems
T May 02	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 1, Greedy 2, Greedy 3
• Dynamic Programming 1, Dynamic Programming 2, Dynamic Programming 3
• Amortized Analysis 1, Amortized Analysis 2, Amortized Analysis 3
• 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.
• Complexity 1, Complexity 2, Complexity 3, Complexity 4, Complexity 5, Complexity 6, Complexity 7
• Undecidability 1, Undecidability 2,
• Algorithmic Problems 1, Algorithmic Problems 2
• Review