positive semi-definite
Last edited: October 10, 2025a matrix is PSD if all eigenvalue are \(\geq 0\), also meaning \(z^{T}K z \geq 0\) for all \(z\).
SISL Talks
Last edited: October 10, 2025Francois
- backpropegation gets worse as time goes on (i.e. local minima); first order system
Streaming Algorithm
Last edited: October 10, 2025Streaming Algorithms are computation that grow with the size of the input at a “small”(?) rate. The memory of these systems is not large—they grow roughly logarithmically or poly-logorithmically against the size of the system.
Every so often as we process our system, we have to output a symbol that tells us about the stream we saw so far.
streaming vs FA
Streaming Algorithms is a superset of DFAs: things that Streaming Algorithms can’t do can’t also be done with DFAs. Their memory doesn’t grow too large against the sizes of strings.
SU-CS161 Midterm Sheet
Last edited: October 10, 2025SU-CS161 OCT092025
Last edited: October 10, 2025Motivating Questions
Can we do better than \(O\qty(n \log n)\) sort?
- What’s our model of computation?
- What are some reasonable models of computation?
comparison based sorting
merge sort, quicksort, insertion sort.
- you can’t access values directly
- you can only compare two items (i.e. if something is better / smaller than another)
Any deterministic, comparison-based sorting algorithm must take \(\Omega\qty(n \log\qty(n))\) steps of computation.
Proof idea—any comparison based sorting algorithm gives rise to a decision tree. The decision tree must have this many steps. The structure of the tree is as follows: nodes are each comparison decision, each nodes has 2 children (one for each ordering between two items), leaf nodes represents the output. The deepest leaf gives the lower bound.