A complex number is a type of number. They are usually written as \(a+bi\).

Formally—

\begin{equation} \mathbb{C} = \left\{a+bi\ \middle |\ a,b \in \mathbb{R} \right\} \end{equation}

This set generates solutions to every single polynomial with unique solutions. Its plane looks like \(\mathbb{R}^{2}\).

constituents

an order pair of two elements \((a,b)\) where \(a,b\in \mathbb{R}\).

properties of complex arithmetic

there are 6. For all statements below, we assume \(\alpha = a+bi\) and \(\beta=c+di\), \(\lambda = e+fi\), where \(a,b,c,d,e,f \in \mathbb{R}\) and therefore \(\alpha, \beta,\lambda \in \mathbb{C}\).

\begin{equation} \begin{cases} x_1’ = 5x_1 - 5x_2 \\ x_2’ = 2x_1 -x_2 \end{cases} \end{equation}

This gives rise to:

\begin{equation} A = \mqty(5 & -5 \\ 2 &-1) \end{equation}

Solving the characteristic polynomial gives:

\begin{equation} (5-\lambda)(-1-\lambda) + 10 = \lambda^{2} - 4\lambda +5 \end{equation}

Therefore, our solutions are imaginary!

\begin{equation} \lambda_{1}, \lambda_{2} = 2 \pm i \end{equation}

Aside: we only need to deal with one

Notably, anything that satisfies the original polynomial, its conjugates also satisfies:

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.