neural network

Like a sound you hear That lingers in your ear But you can’t forget From sundown to sunset

It’s all in the air You hear it everywhere No matter what you do It’s gonna grab a hold on you California soul

\begin{equation} x_1^{(j)} = x_1^{(j-1)} + Attn\qty(x_{k}^{(j-1)}, \forall k) \end{equation}

\begin{equation} At_{x_{1}^{(j-1)}} = \text{softmax}\qty(\frac{q_{1} k_{j}, \forall j}{\sqrt{d_{\ \text{model}}}}) v_{j} \end{equation}

\begin{equation} At_{x_{1}^{(j-1)}} = \text{softmax}_{\text{top-k cliff}}\qty(\frac{q_{1} k_{j}, \forall j}{\sqrt{d_{\ \text{model}}}}) v_{j} \end{equation}

SU-CS161 Things to Review

SU-CS161 Embedded Ethics

Lectures

Divide and Conquer

• SU-CS161 SEP232025

Sorting

• merge sort: SU-CS161 SEP252025
• recurrence solving: SU-CS161 SEP302025
• median: SU-CS161 OCT022025
• randomized algos + quicksort: SU-CS161 OCT072025
• linear time sorting: SU-CS161 OCT092025

Data Structures

• red-black trees: SU-CS161 OCT142025
• hashing: SU-CS161 OCT212025

Graphs

• DFS/BFS: SU-CS161 OCT232025
• Strongly connected components: SU-CS161 OCT282025
• Dijikstra: SU-CS161 OCT302025

DP

• bellman-ford and Floyd-Warshall: SU-CS161 NOV112025
• more DP LCS, knapsack, independent set: SU-CS161 NOV132025

Greedy Algorithms

• greedy algorithms: SU-CS161 NOV182025
• MSTs: SU-CS161 NOV202025

Closing

• Max Flows, Min Cuts, and Ford-Fulkerson: SU-CS161 DEC022025

L = [[start_node]]+[[] for _ in 1 ... n]
start_node.visited = True

for i = 0 ... n-1:
    for u in L[i]:
        for v in neighbor(u):
            if not v.visited:
                v.visited = True
                L[i+1].append(v)

This uses \(O\qty(n+m)\). We can find the shortest paths in \(O\qty(m)\)

Setup: graphs are directed, and edges have “capacities”. We have source vertex \(s\) and sink vertex \(t\).

definitions

s-t cut

A cut is a s-t cuts is for a directed graph it goes from s’s side to t’s side; an edge cross an s-t cuts is the edges that goes from \(s\)’s side to \(t’s\) side

cut cost

the cut cost of an s-t cuts is the sum of the weights of the edges that cross the S-T cut.