CSCE 629 Analysis of Algorithms

• CSCE 629: MWF 3:00-3:50pm, HEB Room 203

General Information

• You can find the syllabus on howdy.
• You can check your grades on ecampus
• The final exam is on Tuesday 12/12/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.
• Brief Introduction to LaTeX
• The Not So Short Introduction to LaTeX

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
• hw8.tex hw8.pdf
• hw9.tex hw9.pdf
• hw10.tex hw10.pdf

Schedule

W Aug 30	Introduction, skim [CLRS] Chap 2, read Appendix A
F Sep 01	Asymptotic Notations, read lecture notes
M Sep 04	Asymptotic Notations, Lower Bounds, read [CLRS] Chapter 8.1
W Sep 06	Lower Bounds, read [CLRS] Chapter 9.1, slides
F Sep 08	Lower Bounds, Divide and Conquer
M Sep 11	Divide and Conquer, Strassen Matrix Multiplication
W Sep 13	Divide and Conquer, FFT
F Sep 15	Divide and Conquer, FFT
F Sep 15	Optional Review: Fast Fourier Transform, Part I
F Sep 15	Optional Review: Fast Fourier Transform, Part II
M Sep 18	Greedy Algorithms
W Sep 20	Greedy Algorithms
F Sep 22	Greedy Algorithms
M Sep 25	Dynamic Programming
W Sep 27	Dynamic Programming
F Sep 29	Dynamic Programming, Quiz on Greedy Algorithms and Matroids
M Oct 02	Amortized Analysis
W Oct 04	Amortized Analysis
F Oct 06	Amortized Analysis, Quiz on Dynamic Programming
M Oct 09	Review
W Oct 11	Midterm Exam
F Oct 13	Graph Algorithms
M Oct 16	Midterm Exam Review, Graph Algorithms
W Oct 18	Graph Algorithms
F Oct 20	Graph Algorithms, Quiz on Graph Algorithms
M Oct 23	Randomized Algorithms
W Oct 25	Randomized Algorithms
F Oct 27	Randomized Algorithms
M Oct	Randomized Algorithms
W Nov 01	Randomized Algorithms
F Nov 03	Computational Complexity
M Nov 06	Computational Complexity
W Nov 08	Computational Complexity
F Nov 10	Computational Complexity
M Nov 13	Computational Complexity
W Nov 15	Computational Complexity
F Nov 17	Approximation Algorithms
M Nov 20	Approximation Algorithms, Undecidability
W Nov 22	No class - University closed
F Nov 24	No class - University closed
M Nov 27	Undecidability, Quiz on Computational Complexity
W Nov 29	Algorithmic Problems
F Dec 01	Algorithmic Problems
M Dec 04	Algorithmic Problems
W Dec 06	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.
• Complexity 1, Complexity 2, Complexity 3, Complexity 4, Complexity 5, Complexity 6, Complexity 7
• Undecidability 1, Undecidability 2