complexity theory is a theory in algorithms to analyze time classes.

older Notes

We know that \(O(n\ log\ n)\) is between \(O(n)\) and \(O(n^2)\) — so we can roughly call it “polynomial time.”

Since the optimal comparison cannot be faster than polynomial time, we say that comparison-based sorting is a polynomial-time algorithm.

From this information, we can come up with two main time classes: \(P\) for solutions with known polynomial time, \(NP\) for non-deterministic polynomial time.

Lectures (SU-CS254)

• SU-CS254 JAN062025
• SU-CS254 JAN082025
• SU-CS254 JAN132025
• SU-CS254 JAN152025
• SU-CS254 JAN222025
• SU-CS254 JAN272025
• SU-CS254 JAN292025
• SU-CS254 FEB032025
• SU-CS254 FEB122025
• SU-CS254 FEB262025

Lectures (SU-CS254B)

A Tour Through 254B’s Complexity Theory

• SU-CS254B MAR312025
• SU-CS254B APR022025
• SU-CS254B APR072025
• SU-CS254B APR092025
• SU-CS254B APR142025
• SU-CS254B APR302025
• SU-CS254B MAY052025

Logistics - 254

• 4 sets (each worth 17.5% for a total of 70%)
• project
  • intern progress report (5%)
  • project report (15%)
  • peer evaluation report (10%)

SU-CS254 project guidelines

• educational
• interest/excite/educate peers
• give thoughtful, constructive feedback, etc.

Logistics - 254B

• Scribing - 30% (1 lecture) “mini project”
  • check plus - 30
  • check - 25
  • check minus - 20
• Group Project - 70% (group, up to 3)

Scribing Details

DUE: 1 week after the relevant lecture, 3PM, prior to lecture.

compositional scene representation is the process of trying to represent a certain visual signal into its constituent parts.

Aim: unsupervised segmentation + representation

• the model finds the most intuitive representations of the scene
• train segmentation and representation together

Autoencoding segmentation! Segment => Represent => Resegment => etc.

Gaussian Mixture Model???? over pixels: regularizes by taking KL Divergence between latent and predicted output, to force them to be similar.

Loss: error in RECONSTRUCTION and KL-Divergence of latent space