An introduction to databases. Logistics Intro Data Models Database Design Phases Bad Design ER Model Drawing ER Diagrams SQL (Structed Query Language) SQL Schema SQL Query Anatomy SELECT and FROM WHERE AS keyword String Operations LIKE ORDER BY Set Operations UNION INTERSECT EXPECT Null Values Aggregation GROUP BY HAVING Nested Subqueries Subquery tests for WHERE Subquery test for FROM DELETE, INSERT, UPDATE DELETE INSERT UPDATE JOINS Natural/Inner Joins Outer Joins Views Integrity Constraints Authorization Privileges Roles Object-relational Databases Complex Types User Defined Types Inheritance Textual Data Big Data Streaming Data Physical Storage Types Interfaces Magnetic Disks Flash RAID RAID Levels Indexing Ordered Indices B+ Tree Hash Indices Transactions Scheduling Query Processing Parsing Optimization Evaluation Relational Algebra Building Execution graph Query Cost Relational Algebra Implementations Selection Sorting Joins Duplicate elimination Projection Set Operations Implementation Outer Join Aggregations Evaluating Expressions Pipelining Logistics Course link ...

Logistics Conventions Newtonian Gravity The Two Body Problem Kepler’s Second Law Kepler’s Third Law From Kepler To Newton The Equivalence Principle Gravitational Redshift Light falls Differential Geometry Definitions/Basics Crash Course Example 2-Sphere Special Relativity Minkowski Spacetime Diagrams Metric Useful Tricks 4-Vectors 4-velocity Dual Vectors 4-momentum Inverse Metric Variational Approach Moving to GR Christoffel Symbols We haven’t done GR yet. Let’s do that Qausi-Stationary Curved or not Curved Tensors General Covariance Useful facts Scalar Field Transformation Vector Field Transformation Dual Vector Transformation Stress-Energy Tensor $T^{\mu\nu}$ Dust Covariant Derivatives Properties of Covariant Derivatives Tidal Forces of Curvature Newtonian GR version Directional Covariant Derivative Reimannian tensor Reimannian Tensor properties Parallel Transport Stress Energy Tensor Conservation EM Force Law Einstein’s Equation What the Heck is $\kappa$? Cosmological Constant Killing Vector Schwarzschild Solution Potential Redshift Lensing An introduction to general relativity. ...

An introduction to plasma physics. Logistics Grading Scheme MHD Equillibrium Consequences of MHD Equillibrium Theta Pinch Z Pinch Screw Pinch Toroidal Geometry Definitions Forces Grad Shafranov Equation Stream Functions Grad Shafranov Derivation Sketch Aspect Ratio Expansion Logistics Location: Mudd 825 Time: 1:10-2:40 Book: MHD Stability of Tokamaks by Zohm Grading Scheme Projects: 60% Homework: 40% MHD Equillibrium Suprisingly useful since particles in plasma undergo gyration, which enhances number of collisions and causes discrete particle to behave more fluid-like Setting time derivatives in MHD equations to zero This is a good assumption, since deviations from this result in motion with timescales on the order of microseconds (called the Alfven time $\tau_{A}$) Hence, if you are physically observe the plasma, good chance it is in EQ $\vec{v} = 0$ is the magneto-static limit (or that $v« v_{a}$) where $v_{a}$ is the Alfven speed (which in turn is defined as size of detector divided by $\tau_{a}$) In space, the magneto-static approximation is normally not valid Define the plasma beta as $\beta = \frac{p}{\frac{B^{2}}{2\mu}}$ or the thermal energy divided by the magnetic field energy Equation of state $P = n_{e}T_{e}+n_{i}T_{i}$ Momentum equation: $\rho(\frac{\partial}{\partial t}\vec{v}+\vec{v}\nabla\cdot \vec{v}) = \vec{J}\times B =\nabla P$ Maxwell’s equations $\nabla \times \vec{B} = \mu_{0}\vec{J}$ $\nabla \cdot B = 0$ $v \times B +E =0 \rightarrow E = 0$ $\frac{\partial }{\partial t} B = -\nabla \times E \rightarrow \frac{\partial }{\partial t} B =0$ Continuity $\frac{\partial}{\partial t}\rho + \nabla \cdot v = 0$ 0=0 Energy $\frac{\partial}{\partial t}P+\vec{v}\cdot\nabla p -c_{s}^{2}(\frac{\partial}{\partial t}\rho + \vec{v}\cdot \nabla \rho) = 0$ To Summarize, for MHD equilibrium, we have that ...

An introduction to solid state physics. Logistics Heat Capacity of Solids Einstein Model of Heat Capacity of Solids Debye Model of Heat Capacity of Solids Electrical Properties (Drude Model) Constant E&M Force Thermal Conductivity Sommerfield Model Fermi-Dirac Statistics Sommerfield Model (cont.) LCAO (Linear Combination of Atomic Orbitals)/ Tight Binding Theory Chemistry Review Shell Theory Ionic Bonds Covalent Bonds LCAO Basics Vibrations 2 Types of Springs Crystal Structure Reciprocal Space Logistics Location: 307 Pupin Time: 2:40-3:55 PM Tuesdays and Thursdays Textbook: The Oxford Solid State Basics Grading Scheme 30% problem sets (5 in total. 1 per 2 weeks) Due on Saturdays at noon 20% midterm Closed book 20% research project presentation 30% final exam Heat Capacity of Solids Heat capacity is defined as $C = \frac{\partial Q}{\partial T}$ For solids, heat capacity at constant pressure and at constant volume are essentially the same, since the atoms are so closely packed For a gas, we have that $\frac{C_{v}}{N} = \frac{3}{2} k_{b}$ For (most) solids, we know that $\frac{C}{N} = 3k_{b}$. Called the law of Dulong-Petit For these derive the above (like Boltzmann did), pretend that we have N atoms trapped in a box. Assume that each atom is trapped within a harmonic potential well of the form $U = \frac{k|\vec{r}|^{2}}{2}$ This arises due to electrostatic forces from neighboring atoms From the equipartition theorem, we have that for every quadratic degree of freedom in the Hamiltonian adds $\frac{k_{b}}{2}$ to the heat capacity For a monoatomic gas, we have 3 quadratic degrees of freedom from the 3 momentum components (position is not a d.o.f. since the particles don’t interact with each other) For solids, we have 6 degrees of freedom, which implies that $\frac{C}{N} = 3k_{b}$ As the tempurature starts to get lower, the tempurature starts to fall of rapidly Einstein Model of Heat Capacity of Solids The main idea is that Einstein used the same model of the N particles in a box, but changed the energy model of the confining potential Instead of $E = \frac{kx^{2}}{2}$, we utilize $E = \hbar \omega(n+\frac{1}{2})$ The original derivation omitted the $\frac{\hbar \omega}{2}$ (ie. the zero point energy), since the Schrodinger equation hadn’t been invented yet $\omega$ is called the Einstein frequency, and is a free parameter of the system Recall the partition function is $Z = \Sigma_{n} exp(-\beta E_{n})$ where $\beta = \frac{1}{kT}$ $<E> = -\frac{1}{Z}\frac{\partial Z}{\partial \beta}$ Plug in energy of quantum harmonic oscillator, turn the crack, and then take derivative w.r.t. temperature yields the specific heat Can define Einstein temperature as $\frac{\hbar\omega}{k_{b}}$, which defines the “freeze out” temperature of the system Problem with this is that at lower potentials, the head capacity goes as $T^{3}$ experimentally, while Einstein is exponential decays Debye Model of Heat Capacity of Solids Basic idea: individual atomic displacements are coupled, which creates a collective excitation/mode which acts like a sound wave The particles which arise from quantizing sound waves are called phonons acts like bosons For sound waves, the dispersion relationship is $\omega = v_{s}|k|$ The average energy is now $<E> =3\Sigma_{k}\hbar \omega(k)(n+\frac{1}{2})$ Namely, now the frequency depends on the wavevector (ie. the dispersion relationship) Can replace sum with integral: $\Sigma = \int 4\pi k^{2} dk$ where k is the magnitude of the wavenumber This comes from assuming periodic boundary conditions, deducing that we have 1 state per every $\frac{(2\pi)^{3}}{L_{x}L_{y}L_{z}} = \frac{(2\pi)^{3}}{V}$ volume in k-space, then converting to spherical coordinates and integrating out solid angle $<E> = 3 \frac{V}{(2\pi)^{3}}4\pi \int_{0}^{\infty} \omega^{2} (\frac{1}{v_{s}})^{3}\hbar\omega(n+\frac{1}{2}) = \int_{0}^{\infty} d\omega g(\omega) \hbar\omega(n+\frac{1}{2})$ Made change of variables from k to $\omega$ $g(\omega) = \frac{12\pi \omega^{2}}{(2\pi)^{3}v_{s}^{3}}V = N\frac{9\omega^{2}}{\omega_{d}^{2}}$ is the density of state Can think of this as the number of modes that exist in the frequency band of $\omega$ and $\omega+d\omega$ $\omega_{d}^{3} = 6\pi^{2}\frac{N}{V}v_{s}^{3}$ Do the tedious integral. The following is useful: $\int_{0}^{\infty} dx \frac{x^{3}}{e^{x}-1} = \frac{\pi^{4}}{15}$ Taking T derivative yields the experimentally observed low tempurature power-law scaling $C_{v} = Nk_{b}(\frac{k_{b}}{\hbar \omega})^{3} \frac{12\pi^{4}}{15} T^{3}$ $k_{b}T_{D} = \hbar \omega_{d}$ Currently, the model blows up at higher tempuratures. Problem is that by integrating to infinity, we are assuming an infinite number of modes. But we are limited by the number of modes present in the system The physical assumption is that $\int_{0}^{\omega_{d}} g(\omega) d\omega = 3N$ ie. there exists a cut-off frequency $\omega_{d}$ that includes all possible modes of the system The integral becomes intractable (ie. must be numerically solved) Problems with model cutoff is a bit ad. hoc. the dispersion relationship is a bit different than sound waves not an exact match The heat capacity of metals follows a different pattern: $\alpha T^{3}+\gamma T$ Electrical Properties (Drude Model) Apply classical kinetic theory to electrons in materials Assumptions Having a scattering time $\tau$ between collisions implies that the probability of a scatter occuring in some dt is $\frac{dt}{\tau}$ After scattering, the averaged momentum of the ensemble is 0 (ie. $<\vec{p}> = 0$) Between scattering events, electrons feel E&M forces since they are charged Consider an electron with some $p(t)$ at time t. We want to know p(t_dt) $(1-\frac{dt}{\tau})(p(t)+Fdt)+\frac{dt}{\tau}*0 = p(t)+Fdt-p(t)\frac{dt}{\tau}\rightarrow \frac{d\vec{p}}{dt} = \vec{F}-\frac{\vec{p}}{\tau}$ Constant E&M Force Let $\vec{F} = q(\vec{E}+\vec{v}\times\vec{B})$ Define current density $\vec{j} = ne\vec{v} \rightarrow \vec{v} = \frac{-\vec{j}}{ne}$ $\vec{E} = \frac{1}{ne}\vec{j}\times \vec{B}+\frac{m}{ne^2\tau}\vec{j}$ First term is an $E_{\perp}$ (Hall field) and second term is $E_{\parallel}$, where we take parallel to be in the flow of the current If B=0, then $\vec{j} = \frac{ne^{2}\tau}{m}\vec{E} = \sigma \vec{E}$ where $\sigma$ is the conductivity (ie. $\sigma = \frac{1}{\rho}$ where $\rho$ is resistivity) $E_{Hall} = =R_{H} \vec{B}\times \vec{j}$ $R_{H} = \frac{-1}{ne}$ Thermal Conductivity $j_{q} = R \nabla T$ is the heat current density For monoatomic gases, $R = \frac{1}{3}nc_{v}<v>\lambda$ $v = \sqrt{\frac{8k_{b}T}{m\pi}}$ Assuming that R of monoatomic gases works for solids, replace v with the appropriate expression Taking the ratio of thermal conductivity to electrical conductivity (called the Lorenz number), we get something on te order of $10^{8}$ called the Wiedemann-Franz law Sommerfield Model Assumptions ...

Creating Bootable USB BIOS Tinkering Setting up Ubuntu Logging In Connecting to the Internet Cronjobs (Auto-Reconnect) Shell Script Adding to Crontab SSH Auto-Update Hardening SSH Enabling password-less Authentication Fail2ban Graphics Over SSH Power External Storage Website Setup Apache2 UFW Github CLI Static IP Port Forwarding Cloudflared Cloudflared DDNS Cronjobs (Website) Automatically pulling from Github Permissions and Configurations Conclusion Previously, I managed to set up this website on a Raspberry Pi SBC clone. While I was able to get the site running and accessible to the internet, the frequent power outages in my neighborhood as well as the fact that my family can mess with the Ethernet connection between the SBC and the router meant that self-hosting was not viable. I also ran out of time during winter break to think of a solution (I also found out that my site didn’t work on the flight back to Columbia, so it was way too late to fix anything). Hence, I ended up using Github Pages as a stopgap measure. ...

Basic CLI commands Vim Cheatsheet Standard Library Functions Compiling and Linking Gcc Header Files Lecture 2 Make Git Lecture 3 Data Types in C Sizeof() Computer Representation of Numbers Signed versus Unsigned Operator Gotchas Precedence Left shift Short Circuit Pre and Post Increment Undefined Behavior Expressions vs Statements Storage Classes Automatic Variables (Local) Static Variables Memory Address Space Stack Data Pointers Void Pointers Faux Pass by Reference NULL pointers Pointer Errata Dangling Pointers Arrays Pointer Arithmetic GUT of Pointers and Arrays Heap Heap Safety Strings String Literals argv Constant Pointers Function Pointers Parsing Function Pointers Structs Unions Typdef Libraries IO Standard I/O Stdout Stdin Stderr Redirection Pipes Files Blocking and Reading Buffering File Seeking Formatted IO Inspecting binary files Endianness Network byte order Forks Reaping Children exec() UNIX Users and Groups Shell Scripts TCP/IP netcat File Descriptors Sockets API Connect Bind, Listen, Accept Send and Receive HTTP/1.0 URLs Command line HTTP requests GET Requests (Client) GET Requests (Server) Status Codes Class Information Course Homepage ...

Ohm’s Law Drude Model Flux Maxwell’s Equations Mutual Inductance Self Inductance Energy in Fields Maxwell’s Equation in Matter Electric Magnetic Boundary Conditions Continuity Equations Charge Energy Momentum Angular Momentum Waves Basic Waves Polarization EM Waves Reflection and Transmission Absorption and Dispersion Absorption Dispersion Wave Guides Potentials Gauge Freedom Coulomb Gauge Lorenz gauge Leinard-Weichart Potentials Radiation Dipoles Point Charges Ohm’s Law $\vec{J} = \sigma (\vec{E}+v\times \vec{B}) \approx \sigma \vec{E}$ $J$ is the current density $\sigma$ is the conductivity $\vec{E}$ is the electric field Microscopic description typically, the velocities are so slow that we can drop the magnetic field term $\vec{I} = \int \vec{J}\cdot \vec{dA}$ ...

Grading Breakdown Heat Equation Steady state solutions Time Dependent Solution Seperation of Variables Laplace Equation Polar Coordinates Mean Value Property Maximum Principle Fourier Series Convergence Term by Term Differentiation Solving Inhomogeneous Equations Wave Equation Strum Liouville Theory SL properties Green’s Identity Minimization Principle Parseval’s Identity Bessel’s Identity Multi-Dimensional PDEs Green’s Identity (Higher Dimensions) Polar Coordinates Bessel’s equation Fourier Transforms Green’s Functions Heat Equation Case Study Dirac Delta Green’s Function via Differential Equation Nonhomogeneous BCs Green’s Function via Eigenvalue Expansion Fredholm Alternative Grading Breakdown HW: 40% Assigned on Monday weekly. Due next monday Exams: 20% each Textbook: Haberman: Applied Partial Differential Equations Heat Equation Basic physical principle: Convervation of energy The change in energy over time = flow of heat energy (flux) across the boundaries The total heat energy at time t is the integral of the temperature over the domain: $E = \int_{a}^{b} u(y,t) dy$ The time derivative w.r.t. E then equals the heat flux as per Fourier’s law $\epsilon(x,t) = -K(x)\frac{\partial u}{\partial x}$ $K(x)$ is the thermal conductivity Therefore, heat equation becomes: $\frac{\partial u}{\partial t} = -K(x) \frac{\partial^{2} u}{\partial x^{2}}$ To get a complete solution you need initial conditions and boundary conditions Initial conditions: $u(x,t=t{0}) = f(x)$ Boundary conditions: Dirichlet: Temperature is prescribed Neumann: Derivative of temperature is perscribed Steady state solutions Assuming that the steady state exists, just drop all time derivatives to reduce 1D heat equation to ODE. Dirichlet: Solution becomes a linear interpolation between ends of rod Neumann: Need to use conservation of heat energy to relate initial energy (derived from integrating initial condition) to final energy (derived from integrating steady state solution) To get something physical, we also demand the following: Temperature is continuous ($lim_{x\rightarrow x_{0}-} u = lim_{x\rightarrow x_{0}+} u$) Heat flow is continuous ($lim_{x\rightarrow x_{0}-} K(x) \frac{\partial u}{\partial x} = lim_{x\rightarrow x_{0}+} K(x) \frac{\partial u}{\partial x}$) Time Dependent Solution Seperation of Variables Assume that the tempurature can be split into a time dependent part and a space dependent part: $u(x,t) = X(x)T(t)$ Suppose that we have the boundary conditions $u(0,t) = u(L,t) = 0$. This implies that $X(0) = X(L) = 0$ Plugging in potential solution results in two ODEs that equal to each other. This implies that each individually equals a constant. rearranging yields: $X^{’’} = c X$ If c<0, then solutions of the form $X(x) = A exp(i\lambda x)+ B exp(-i\lambda x)$ where $-\lambda^{2} = c$ If c>0, then solutions of the form $X(x) = A exp(\lambda x)+B exp(-\lambda x)$ where $\lambda^{2} = c$ $T^{’} = cKT$ Solutions of the form $T(t) = T(0)exp(ckt)$ For the boundary conditions that we have, only the oscillating solutions are physical. Can solve for A,B and c via boundary conditions General solution comes from taking a linear combination of these solutions: $u(x,t) = \Sigma_{n=0}^{n=\infty} c_{n} T(t)X(x)$ $c_{n}$ can be computed using the orthogonality of sin and cos: $\int_{-L}^{L} \sin(\frac{n\pi x}{L})\cos(\frac{m\pi x}{L}) dx = 0$ $\int_{-L}^{L} \cos(\frac{n\pi x}{L})\cos(\frac{m\pi x}{L}) dx = \frac{L}{2}\delta_{nm}$ $\int_{-L}^{L} \sin(\frac{n\pi x}{L})\sin(\frac{m\pi x}{L}) dx = \frac{L}{2}\delta_{nm}$ Laplace Equation $\nabla^{2} u = \frac{\partial^{2} u}{\partial x^{2}}+\frac{\partial^{2} u}{\partial t^{2}} = 0$ Suppose that the following Dirchlet BC’s hold: $u(0,y) = f_{1}(y)$ $u(L,y) = f_{2}(y)$ $u(x,0) = g_{1}(x)$ $u(0,L) = g_{2}(x)$ Using seperation of variables, we know from the heat equation that the following solution works: $u = v(x)w(y)$ $w(y) = \sin(\frac{n\pi y}{L})$ $v(x) = C_{1}exp(cx)+C_{2}exp(-cx)$ $c = (\frac{n\pi}{L})^{2}$ General solution is then $u(x,y) = \Sigma A_{n} \sinh(\frac{n\pi x}{L}) \sin(\frac{n\pi y}{L})$ Polar Coordinates $\nabla^{2} u = \frac{1}{r}\frac{\partial}{\partial r}(r \frac{\partial u}{\partial r})+ \frac{1}{r^{2}}\frac{\partial^{2} u }{\partial \theta^{2}} = 0$ BCs: $u(r,\pi) = u(r,-\pi)$ $\frac{\partial}{\partial \theta}u(r,\pi) = \frac{\partial}{\partial \theta}u(r,-\pi)$ Using separation of variables: $u = R(r)\Theta(\theta)$ $u(r,\theta) = \Sigma_{n=0}^{\infty} A_{n} r^{n} \cos(n\theta)+ \Sigma_{n=0}^{\infty} B_{n} r^{n} \sin(n\theta)$ Mean Value Property Assuming Dirchlet BCs, the value at center of disc is equal to the average value on the edge of the disk: $u(0,\theta) = \frac{1}{2\pi}\int_{-\pi}^{\pi} u(\alpha,\theta) d\theta$ This holds for all sub disks centered on the disk (mean value property) Let $U(w) = \frac{1}{2\pi}\int u(x_{0}+w \cos (\theta),y_{0}+w \sin (\theta)) d\theta$ This is the average value on a circle of radius 2 centered at $x_{0},y_{0}$ Taking $\frac{d}{dw}$ of the above, applying chain rule, and rewriting as a dot product Making the substitution $\vec{n} = (\cos\theta,\sin\theta)$ and applying the divergence theorem, and applying Laplace’s equation $\nabla^{2} u = 0$, we see that $\frac{dU}{dw} = 0$. Hence, the mean value property holds on any disk on the region Maximum Principle Laplace’s equation can only have an extrema on the boundary of the domain (unless it is constant everywhere) Fourier Series Assuming that a function is bounded and piecewise continuous, then it can be approximated as a Fourier series. If we bound the function to the domain [0,L], then the function can be written as $f(x) = a_{0}+\Sigma a_{n}\cos(\frac{n\pi x}{L})+\Sigma b_{n} \sin(\frac{n\pi x}{L})$ the coefficients can be found via Fourier trick In the case of jump discontinuities, then the Fourier series converges to the average of the left and the right limits We can extend the function to the domain [-L,L] in two ways: in an even manner (cosine series) or an odd manner (sine series) If f(x) is bounded and is smooth on [-L,L] The fourier series is continuous and converges to f(x) iff f(x) is continuous and $f(-L) = f(L)$ The Fourier cosine series is continuous and converges to f(x) on the interval [0,L] iff f(x) is continuous on interval (assuming even extension) The Fourier sine series is continuous and converges to f(x) on the interval [0,L] iff f(x) is continuous on interval and f(0) = F(L) = 0 (assuming odd extension) If f(x) solves a PDE, then it’s Fourier series also solves the PDE (and vice versa) Convergence The Fourier series converges to f(x) iff it is bounded and piecewise smooth Bounded means there is a constant $M\geq 0$ such that $|f(x)|<M$ on the entire domain of f piecewise smooth means that the interval can be broken up into a finite number of pieces, were on each subinterval, f(x) and f’(x) are continuous On an interval from -L to L, the Fourier series converges if f is continous, or it converges to the average of the left and right limits of f has a jump discontinuity This extends to the periodic extension of f(x) Term by Term Differentiation Useful for solving inhomogeneous PDEs The following are necessary conditions for term by term differentiation to be valid f(x) continuous on interval $[-L,L]$ f(L) = f(-L) Solving Inhomogeneous Equations Suppose that we have a nonhomogenous heat equation with source g(x) $\frac{\partial u}{\partial t} = \kappa\frac{\partial^{2} u}{\partial x^{2}}-\alpha u +g(x)$ IC $u(x,0) = f(x)$ BC $\frac{\partial u}{\partial t}(0,t) = 0 = \frac{\partial u}{\partial y}(L,t)$ Due to the Neumann BCs, assume a consine series solution exists for f(x), g(x) and u(x) Use term by term differentiation to solve for coefficients of $u(t)$ Wave Equation $\frac{\partial^{2} u}{\partial t^{2}} = c^{2} \frac{\partial^{2} u}{\partial x^{2}}$ c defines the wave speed Suppose BCs where u is fixed to 0 at x=0 and x=L Use separation of variables to solve problem $u(x,t) = \Sigma_{n=1}^{\infty} [A_{n}\cos(\frac{n\pi c t}{L})+B_{n}\sin(\frac{n\pi c t}{L})] \sin(\frac{n\pi x}{L})$ $A_{n}$ and $B_{n}$ come from IC via Fourier trick Can rewrite above in terms of normal modes (ie. standing wavees) $u(x,t) = \Sigma_{n=1}^{\infty} [\sqrt{A_{n}+B_{n}}\sin(\omega t+\theta)] \sin(\frac{n\pi x}{L})$ $\omega = \frac{n\pi c}{L}$ $\theta = tan^{-1}(\frac{A_{n}}{B_{n}})$ Each standing wave can be rewritten as two travelling waves $\sin(\frac{n\pi x}{L})\sin(\frac{n\pi c t}{L}) = \frac{1}{2}[\cos(\frac{n\pi}{L}(x-ct))-\cos(\frac{n\pi}{L}(x+ct))]$ Total energy is conserved: $E(t) = \frac{1}{2}\int|\frac{\partial u}{\partial t}|^{2} dx+\frac{c^{2}}{2}\int |\frac{\partial u}{\partial x}|^{2} dx$ Strum Liouville Theory Strum Liouville problem defined as $\mathbb{L}[\phi](x) = \lambda \sigma(x) \phi(x)$ $\mathbb{L}[\phi](x) = -\frac{d}{dx} (p(x) \frac{d\phi}{dx})-q(x)\phi(x)$ p,q, $\sigma$ are real functions on interval, including boundary p(x) >0 and $\sigma(x)$ >0 for all x in open interval Additional constraint of $q(x) \geq 0$ defines a regular SL problem BCs $\beta_{1} \phi(a) +\beta_{2} \frac{d\phi}{dx}(a) = 0$ $\beta_{3} \phi(b) +\beta_{4} \frac{d\phi}{dx}(b) = 0$ $|\beta_{1}|^{2}+|\beta_{2}|^{2} \neq 0$ $|\beta_{1}|^{3}+|\beta_{1}|^{4} \neq 0$ One can transform a general 2nd order ODE to Sl problem Let $R(x)\frac{d^{2}\phi}{dx^{2}}+P(x) \frac{d\phi}{dx}+Q(x) \phi = \lambda \delta(x) \phi$ The above becomes an SL problem, where $p(x) = exp(\int \frac{P(x)}{R(x)})$ $q(x) = p(x) \frac{Q(x)}{R(x)}$ $\sigma(x) = p(x) \frac{\delta (x)}{R(x)}$ SL properties All eigenvalues $\lambda$ are real There are infinitely many eigenvalues with some hierarchy such that $\lambda_{n} < \lambda_{n+1}$ Hence, there is some smallest eigenvalue $\lambda_{1}$ $\lambda_{n}$ goes to infinity as n goes to infinity For each $\lambda_{n}$, there exists some $\phi_{n}(x)$ as it’s associated eigenfunction with exactly $n-1$ zeroes on the interval The eigenfunctions for a complete basis, so that any function on the interval can be written as $f(x) = \Sigma_{n=1}^{\infty} a_{n} \phi_{n}(x)$ The eigenfunctions follow an orthogonality relationship $\int_{a}^{b} \phi_{n} \phi_{m} \sigma dx = A \delta_{mn}$ The Rayleigh quotient relates the eigenfunction to it’s eigenvalue: $\lambda = \frac{-p \phi \frac{d\phi }{d x} \bigg |_{a}^{b} +\int _{a}^{b} [p(\frac{d\phi}{dx})^{2}-q\phi^2]}{\int _{a}^{b} \phi^{2} \sigma dx}$ Green’s Identity $\mathbb{L}[\phi](x) = -\frac{d}{dx} (p(x) \frac{d\phi}{dx})-q(x)\phi(x)$ The following holds for SL problems for any two functions u,v $u \mathbb{L}[v]-v\mathbb{L}[u] = -\frac{d}{dx}(p(x) (u\frac{dv}{dx}- v\frac{du}{dx}))$ If $\int _{a}^{b} u \mathbb{L}[v]-v\mathbb{L}[u] = 0$, then $\mathbb{L}$ is said to be self-adjoint With regular SL BCs, $\mathbb{L}$ is always self adjoint Minimization Principle For $n >1$ for regular SL problems, we have that $\lambda_{r} = min RQ[v] = min_{v} \frac{\int _{a}^{b} v\mathbb{L}[v]dx}{\int _{a}^{b} v^{2} \sigma dx}$ where we are minimizing over all functions v which satisfy the BCs Hence, if we find some v which satisfies the BCs, we can set an upper bound on $\lambda$ For reasonable upper bounds, v should be greater than 0 over entire domain Parseval’s Identity $\int_{a}^{b} |f(x)|^{2} \sigma(x) dx = \Sigma_{n=1}^{\infty} a_{n}^{2} \int_{a}^{b} |\phi_{n}|^{2} \sigma(x) dx$ $f(x) = \Sigma_{n=1}^{\infty} a_{n} \phi_{n} (x)$ Bessel’s Identity $\int_{a}^{b} |f(x)|^{2} \sigma(x) dx \geq \Sigma_{n=1}^{M} a_{n} \int_{a}^{b} |\phi_{n}|^{2} \sigma dx$ Multi-Dimensional PDEs $\frac{\partial y}{\partial t} = \kappa \nabla^{2} u$ (heat equation) $\frac{\partial^{2} u}{\partial t^{2}} = c^{2} \nabla^{2} u$ (wave equation) $\nabla^{2} = 0$ (Laplace equation) Some homogeneous problems with seperation of variables just like before For homogeneous problems with source terms, expand the source term w.r.t the eigenfunctions of the normal homogeneous case, expand the ICs the same way, then solve for the coefficients using term by term differentiation Green’s Identity (Higher Dimensions) let $\mathbb{L}[u] = \nabla^{2} u $ Recall that $<x,y> = \int x y dV$ $<u, \Delta v> -<\Delta u, v> = \int [u(\Delta v \cdot \vec{n})-v(\Delta u\cdot\vec{n})] dS$ The associated Rayleigh Quotient is then $RQ[u] = \frac{<u, \mathbb{L[u]}>}{<u,u>_{\sigma}}$ Polar Coordinates Suppose we have the eigenproblem $-\nabla^{2} u = \lambda u$ in polar coordinates Using seperation of variables, we must solve the following ODEs $\frac{r}{f} \frac{d}{dr}(r \frac{df}{dr}) + \lambda r^{2} = \frac{-1}{g} \frac{d^{2}g}{d\theta^{2}} = \mu$ We recognize the r diff eq. as an SL problem, with $p = r$, $q = \frac{-\mu^{2}}{r}$ and $\sigma(r) = r$ Bessel’s equation Make the change of variables $f(r) = h(\sqrt{\lambda} r)$ to arrive at the equation $z^{2} \frac{d^{2} h}{dz^{2}} + z \frac{dh}{dz} + (z^{2}-\mu^{2})h = 0$ (called Bessel’s equation) The general solution to Bessel’s equation is $h(z) = c_{1} J_{m}(z) +c_{2}Y_{m}(z)$ $J_{m}$ are called Bessel functions of the first kind, and have well defined asymptotic behavior as z approaches 0: $J_{m}(z) \approx 1$ if $m=0$ as z approaches 0 $J_{m}(z) \approx \frac{z^{m}}{2^{m}m!}$ if $m >0$ as z approaches 0 We denote the roots of $J_{mn}(z)$ as $\rho_{mn}$ $Y_{m}$ is unbounded at z = 0 $Y_{m}(z) \approx \frac{2}{\phi} ln(z)$ if $m=0$ as z approaches 0 $Y_{m}(z) \approx \frac{-2^{m} (m-1)!}{\pi z^{m}}$ if $m >0$ as z approaches 0 Fourier Transforms We define the Fourier transform (in this class) as follows: ...

Compilation of notes for Fundamentals of Computer Systems class for Spring 2023. Problem Solving Tips Administrative Stuff Exams Grades Lecture 0 Lecture 1 CPU Models Addition in different bases Definitions Modular Arithmetic Integer format with word size restriction Unsigned binary numbers Binary Addition Algorithm (BAA) Negative numbers Signed Magnitude Representation 1’s Complement Problems with Signed Magnitude and 1’s Complement 2’s complement Intuition behind 2’s complement Lecture 2 Why 2’s complement? Easy subtraction Detecting Overflow Floating Points IEEE standard for a 32 bit word Doubles Underflow Boolean Algebra Boolean Algebra Identities Distributive Law Proof DeMorgan’s Theorem Consensus Theorem circuit Representation of Boolean Algebra Coverting Circuits to Booleans NAND and NOR XOR Duals Lecture 3 Sum of Products (SoP) Product of Sums (PoS) Convert SoP to PoS Minterms Maxterms Karnaugh Map K-map Notation Summary of Simplification with k-maps 2-bit multiplier Don’t Care Conditions Drawing Circuits Lecture 4 Standard Circuits Enabler Decoder Circuit Decoder With Enable MUX (Multiplexer) Representing Functions with Decoders and MUXes MUX trick Shifter Circuit Barrel Shift left w/ Wraparound L-R Shift Circuit with Rollout Unsigned Adder Circuit Half-Adder Full-Adder Signed Adder/Subtractor (2’s-C) Ripple Carry Adder Optimizing Ripple Carry (Carry Lookahead) Merge with known 0’s Code Converter Contraction Example 1 Lecture 5 Latch Intuition SR Latch SR Latch with Control D Latch with control Latches Can’t be Clocked Flip Flops JK Flip Flop (JKFF) Flip Flop Table Trigger Types Sequential Circuit State Machines Registers Register MUXing Shift Register Ripple Counter PLA (Programmable Logic Devices) MIPS Programming Parts of a Program Computer Hardware CPU Memory Clock ISA (Instruction Set Architecture) Programming in MIPS Instruction Types Memory Pointers $pc sp Constants Sign-extend Pseudoinstructions Things to Remember Assembly Code ALU Details of Memory Single Memory Cell Coincident Selection Extending Memory Why is memory not clocked? Architectures Single Cycle Architectures (SCA) Control Control Flow Pipelines MIPS Dependencies Hazards Implementing Hazard Correction Caching Locality Blocks Cache Hits and Misses Direct mapping Fully Associative Caching Set Associative Caching Writing to Main Memory Virtual Memory Problem Solving Tips Break down problems into manageable sub-problems If you get stuck, take a break, then slowly and methodically think through the sticking point (ie. break it down more. Make sure you are reading the problem correctly) Write in your own words what you need to do Remember that everything happens in parallel, and you only keep the results that you want Administrative Stuff Exams Midterm: On March 8th, 6-9 pm (tentative) Check for conflicts End-of-term exam: Either April 27, evening (6-9 pm) or May 5 in the evening Fill in exam conflicts (by 1/24) Acceptable excuses: conflicting classes and religious conflicts Fill in P-credit office hours (By 1/21) Go to web form The top row indicates the start time of the office hours (e.g. 12 means 12-1. 12:30 means 12:30-1) Need at least 10 hours selected Email for help: 3827-staff[at]googlegroups.com Include 3827 in subject header. Otherwise, it will get overlooked Use EdStem for class updates instead of Courseworks, as well as to ask questions b/c it will be faster than email Grades P Credit has a score between 0 to .3 P = 0 you never attend P = .3 you attend every P-cred and actively participate The final grade is G = 100P+(1-P)(10H+max(30M+60F,45M+45*F)) H is the percent correct on the HW M is the percent correct on the midterm F is the percent correct on the final Lecture 0 Work on HW0 (Not graded) Why should I care about this course? Shows how computers run “under the hood” Learn “parallel thinking” Humans think sequentially Circuits run multiple “threads” at once Useful to understand these ideas in many domains Systems Programming Languages (Compilers and Interpreters) Quantum Computing ML/AI Lecture 1 CPU Models CPU: “brain” of the computer Control Unit: D oes calculations on data in datapath Memory: Stores data (for later use) I/O: Interface to the outside (disk, network, monitor, keyboard, mouse, etc.) Simpler model of CPU: Discrete inputs (over time) Discrete Information Processing System communicates with System state and output something based on input System State Remembers previous information Addition in different bases humans: 10 digits: {0,1,2,3,4,5,6,7,8,9} $(4537.8)_{10} = 4*10^{3}+5*10^{2}+3*10{1}+7*10^{0}+8*10^{-1}$ Shifting everything to the left is multiplication by 10 computers: 2 digits: {0,1} $(1011.1)_{2} = 1*2^{3}+0*2^{2}+1*2^{1}+1*2^{0}+1*2^{-1} = 11.5$ Shifting everything to the left multiplies by 2 Hex: 16 digits {0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F} Hex numbers specified as 0x26BA $0x26BA = 2*16^{3}+6*16^{2}+11*16^{1}+10*16^{0} = (9914)_{10}$ We use hex since it is more human readable and is easy to convert to and from binary a base-2 4 digit can be multiplied by 16 by shifting 4 to the left ($1100 \rightarrow 1100\ 0000$) a base-16 1 digit can be multiplied by 16 by shifting 1 to the left ($0xD \rightarrow 0xD0$) To convert binary to hex, break hex into groups of 4 and convert each group to corresponding binary number $0010\ 1011 \rightarrow 0x2B$ For hex to binary, just convert each hex digit to the corresponding group in binary $0x2B \rightarrow 0010\ 1011$ Definitions True = 1, False = 0 Everything eventually converted to either 1 or 0 Numbers: 19 base 10 = 10011 base 2 Letters: each character is assigned to a 8 bit number Bits: a single binary digit (0 or 1) The leftmost bit is the highest order bit The rightmost bit is the lowest order bit Byte: A group of 8 bits. e.g. (10110010) Word: a grouping of bits computer-architecture dependent The number of bits that the computer architecture can process at once 64-bit word architectures expect data in 64-bit groupings The number of bits used by an architecture is called the word size Common notation for k-bit value: $b_{k-1}b_{k-2}…b_{1}b_{0}$ Modular Arithmetic Def: X mod Y = remainder (X/Y) remainder constrained between 0 and Y-1 Alternative definition: remainder constrained between $-\frac{Y}{2}$ and $\frac{Y}{2}-1$ 100 mod 9 = 1 -10 mod 3 = -1 mod 3 = 2 mod 3 X mod Y = Z mod Y iff $X = Z+KY$ for some integer K Integer format with word size restriction For a given number of digits, how many possible values can you represent? $b^{d}$, where b is the base and d is the number of digits For 2 bit word size: {00, 01, 10, 11} As humans, we can assign whatever value to a distinct bit-sequence: 2 bit word size: {00: .234, 01:i, 10: 234, 11: asdf} Nonsensical , but allowed Unsigned binary numbers Positive integers of a fixed wordsize e.g. 1111 = 15 for a 4-bit word Binary Addition Algorithm (BAA) 1+1 = 0 with a carry of 1 eg. wordsize = 5, add 11110 and 10101 (30+21) 11110+10101 = 10011 if restricted to 5 bits Called overflow: when a result can’t fit within the wordsize constraint The correct answer needs 6 bits (110011) The answer may not be correct because of overflow, but it is correct up to mod $b^{d}$ Negative numbers Signed Magnitude Representation Let the highest order bit denote the sign of the number (0 is positive and 1 is negative) e.g. 0011 = 3 e.g. 1011 = -3 e.g. 1000 = 0000 = 0 To negate, simply flip the highest order bit 1’s Complement Again, highest order bit indicates sign (0 is positive and 1 is negative) To negate a value, flip all the bits 0010 = 2 1101 = -2 e.g. wordsize of 8, value is 11101001. 1’s Complement rep We know its negative (1 in highest order) Negate all the bits and read off positive value, then slap on negative sign Using this, 11101001 = -20 000000 = 111111 are both 0 in 1’s complement Problems with Signed Magnitude and 1’s Complement 0101+1101 = 0010 (after dropping carry of 1) Unsigned binary: 5+8 = 2 (correct mod 16) Signed magnitude: 5+ (-5) = 0 (not 2, even up to mod 16) 1’s complement: 5+(-2) = 3 (not 2, even up to mod 16) TL;DR Binary Addition Algorithm doesn’t work 2’s complement highest order bit is still sign To negate a number, flip all the bits (like 1’s complement) then add 1 in binary (eg a 4 bit word size, you add 0001) 0010 = 2 so 1101+0001 = 1110 = -2 1101 = -3 so 0010+0001 = 0011 = 3 (works for negative) 0 is unique in 2’s complement (0000 = 1111+0001 = 0000) “100000” maps to itself in 2’s complement (largest negative number of the word size) 2’s complement always work with BAA (meaning that with any overflow, the result is off by mod $2^{wordsize}$) Intuition behind 2’s complement Let X be some word of size k Negate all the bits of X and call it Y e.g. X = 100101, so Y = 011010 $X+Y$ using BAA always equals a a word of size k whose entries are entirely 1s $X+Y$ = 111111 Adding the the decimal number 1 to $X+Y$ (ie 000001) causes overflow which yields a word of only zeros. So we can think of the operation of flipping all the bits and adding decimal 1 to a string as the negation of X Lecture 2 The range of unsigned integers is 0 to $2^{k}-1$ The range of signed integers is $-2k^{k-1}$ to $2k^{k-1}$ A string if bits is useless unless you know what representation they represent (unsigned, signed ,ASCII, etc.) Representation: How you interpret the bits Operations: do something to the bits (independent of representation) Why 2’s complement? Easy subtraction Say that we want to find 001110-010101 in signed magnitude representation (14-21). It the same procedure as in base 10, but in base 2 (including carries) Instead, make the representation the 2’s complement Negate 21, then apply BAA. You get the correct answer: 001110-010101=001110+101011=111001 (14-21=7) Detecting Overflow For 2’s complement: Look at the final 2 carries from the BAA algorithm. If the carries are different, you have overflow $00$ case: $5+1=6\rightarrow 0101+0001=0110=6$ $11$ case: $-5-3=-8\rightarrow 1011+1101=1000=-8$ $10$ case (overflow): $-2+-7=-9\rightarrow 1110+1001=0111=7$ $01$ case (overflow): $7+7=14\rightarrow 0111+0111=1110=-6$ Overflow just means that the result can’t be represented with the word size. It does not mean that the result is too big Floating Points Scientific notation: -7.776E3. The number to the left of the E is called the mantissa. The number to the right is the exponent In binary: $-1.10\times2^{01111}= -1.5*2^{7}$ IEEE standard for a 32 bit word highest order bit (31th) is the sign 0 is positive, 1 is negative exponent is bit 30 to 23 represent the value as an unsigned binary, then subtract 127 (the bias) Fraction (the rest of the bits) represents 1.XXXXXX. The “1.” is implicit for all floating point numbers, including zero. The mantissa represent the numbers after the decimal To approximate zero, you set all the bits to zero, which corresponds to $1.0*2^{-127}$, which is effectively zero Doubles A double uses two 32-bit words There is one sign bit, 11 exponent bits, and 52 fraction bits The first word has the sign bit, the exponent bits and the rest are the higher order bits of the fraction The second word is the rest of the fraction The bias is 1023 Underflow Say that we have a number X = 1E-83. Squaring X, we get Y = 1E-166. This cannot be represented as a float. This is referred to as underflow, which is a subcategory of overflow Boolean Algebra Either 0 or 1 (False or True) Can represent as a variable (X,Y,A,B) Complement of X is denoted as $\bar{X}$. This is just flipping a bit Literal a boolean variable or its complement $\cdot$ represents AND (can be omitted) + represents OR Left to right precedence. parentheses give priority to operations You daisy chain operations on multiple values by constructing a truth table where each column represents an unsigned integer Expressions is a set of literals (possibly with repeats) combined with logic operations Equations expression1=expression2 Functions: Takes in some literals and outputs an expression Boolean Algebra Identities $X+XY=X$ $X(X+Y)=X$ Distributive Law Proof $(X+Y)(X+Z) = XX+XZ+YX+YZ$ Apply $XX=X$, $X+XZ = X$, $X+YX=X$ sequentially to show final result DeMorgan’s Theorem Split the big bar at the operator Chance AND to OR and OR to AND Flip-flop literal 0 and 1 to each other Replace function F with the complement $\bar{F}$ and vice versa Consensus Theorem $XY+\bar{XZ}+YZ=XY+\bar{X}Z$ If $YZ = 0$, then trivially you can drop $YZ$ If $YZ=1$ both $Y$ and $Z$ are 1. $XY+\bar{X}Z+1 = 1$, so LHS is 1 Either $X$ or $\bar{X}$. Since $Y=Z=1$, either $XY$ or $\bar{X}Z$ is 1, so RHS is 1 circuit Representation of Boolean Algebra The depth of a circuit refers to how the maximum layers are between the input and output If you want to have multiple inputs, put more lines as the input on the left a k-input gate has a depth of $log_{2}(k)$ Coverting Circuits to Booleans Start from the RHS and move left As you pass each gate, write down the number of inputs in their own section Repeat until you get to your inputs NAND and NOR You invert the output of AND and OR respectively These are universal gates XOR XOR is denoted as $\otimes$ (either the first or the second is true, but not both) Used for parity control (how many of the inputs are true) $Y\otimes 0 = Y$ $Y\otimes 1 = \bar{Y}$ $X_{1}\otimes X_{2}\otimes…X_{k}=1$ when an odd number of $X_{i}=1$ Duals All booleans expressions have duals. TO construct the dual: Swap the ANDs and ORs, swap the literals 0 and 1 for each and rearrange the parentheses as needed You can take the complement of a function by taking the dual, then negating all the literals Lecture 3 Sum of Products (SoP) Any function can be represented as a product of sums (ie. ORing ANDS together) Do all the ANDs before the ORs To calculate, expand out all the terms, then remove duplicates G = X(Y+Z)(X+Y+Z) = XY+XZ Product of Sums (PoS) Any function can be represented as a sum of products (ie. ANDing many ORs together) Do all the ORs before the ANDs Convert SoP to PoS onvert function $F$ to SoP. Take the compliment of SoP by taking the dual and then complementing the literals. This is PoS Minterms Minterm is a product term in which all variable appear exactly once (either complemented or uncomplemented) You can refer to each minterm by the unsigned int that they represent (mX) A function can be described as a sum of its minterms You can evauluate when the function is true by looking at the minterms You can marginalize on a literal by including the minterms that include literal and its complement Minterm expansion is not a simplified form Maxterms The dual of minterms (ie a sum in which all variables appear exactly once, either complemented or uncomplemented) Denoted as MX The product expansion of a function in terms of maxterms Whenever the function evaluates to zero, these inputs correspond to a particular maxterm in the expansion Karnaugh Map Say that you have $F = X+\bar{X}Y$. How do you simplify this? Replace $X = X+XY$ and turn the crank to get $F=X+Y$ Not immediately obvious. Need an automatic tool to help Not the simplest form, but good enough Expand the truth table into a 2D grid indexed Y horizontally and X vertically (origin from the top-left and moves right and down) Each value of the input literal tells you where on the Karnaugh Map Let the vertical axis be X, and the horizontal be YZ Gray encoding: order values of YZ such that only one bit changes at a time Y goes on top, Z goes on bottom Minterm product terms correspond to a $2^{i} \times 2^{j}$ rectangle (including wraparounds) To find the simplest form you can derive from the k-map, you draw the largest rectangles you can (incluing wraparounds) and then relate these rectangles to products K-map Notation Implicant: a product term comprised of minterms for which the function F evaluates to 1 (ie. a box whose dimensions are powers of 2) Prime Implicant: there exists no other implicant that can contain this implicant Essential Prime Implicant: this implicant covers at least one minterm that is not covered by any other prime implicant Summary of Simplification with k-maps Identify all the prime and essential prime implicants Include all the essential PIs If any 1-valued minterms are uncovered by EPIs, choose PIs that are “big” and do a good job covering Heuristic: Choose the PIs that minimize overlap with one another and with EPIs 2-bit multiplier You have 2 2 bit numbers. You need 4 bits to represent the largest product Each bit in the output can be written as a k-map, which can be simplified to write what inputs correspond to this particular output bit getting turned on Don’t Care Conditions These are circumstances where the output doesn’t matter Going to the 2-bit multiplier, say that you know that some set of inputs will never occur. Hence you can ignore the output of those inputs when building a circuit Denote X as the outputs where you don’t care about the output In the k-map, replace the don’t care conditions with X. You can optionally cover X’s with EPI’s (ie. you can include X’s in larger boxes to simplify circuitry) Drawing Circuits Denote a circuit as a blob so you don’t have to redraw a circuit over and over again When an input changes, it takes time for the output to get updated Lecture 4 Standard Circuits NB: Think about circuits as having constant input Enabler Takes in data D (k bits in parallel), as well as an enable/disable trigger E. There is a single output of k bits If E=1, the output equals the input If E=0, output equals k 0’s Implement enabler with k AND gates. Each input has it’s own AND gate, and the other pin is the Enable input Decoder Circuit Takes in a k-bit input and $2^{k}$ 1-bit outputs The selector indicates as an unsigned binary which output = 1. All other outputs are zero Write truth table out. Each row is a minterm. Recall that each minterm evaluates for 1 for a unique combination of literals. You can write decoders with a combination of NOTs and ANDs Decoder With Enable Slap the two previous circuits together Push the output of the decoder through k AND gates where every AND gate has a input connected to the enable pin MUX (Multiplexer) Takes $2^{k}$ 1-bit data values as input. Has a k-bit selector that indicates in unsigned binary which data bit is output You push all the data values in as input simultaneously, and only the one you select is the output. All other inputs are dropped You have a selector part that chooses which input to select You pass all this data to an enabler, whose output gets passed to an OR gate Representing Functions with Decoders and MUXes Use a Decoder and OR together the minterms that evaluate to 1 of your function Use a Multiplexer where you feed in the output of your function. The input to the multiplexer is the values that your literals you take. The output is then your function MUX trick Look at your truth table in pairs of rows. You can select on A and B as the selector input. You pass the C input as one of the the $2^{k}$ 1-bit inputs and it’s complement Shifter Circuit k-bit data value enter as input l-bit selector in unsigned binary tells how many bits to shift k-bit output where bits are shifted by l-bits (can wraparound or drop out) Barrel Shift left w/ Wraparound Say you want to shift over by 2 with wrap around You use MUXes. Each output bit of the MUX goes to the output of the Shifter. All the MUXes have the same shift bit as their selector L-R Shift Circuit with Rollout ...