December 14, 2013

My SteamOS Experience

SteamOS

After quite a bit of fighting, I have managed to create a stable, working SteamOS installation, on which I am writing this blog post. In the interest of science! I will be detailing the steps I took while installing the OS, along with all the issues I had and how I solved them. To help anyone trying to troubleshoot things, here are a list of things that went wrong. If you want to know how they were fixed, keep reading:

  • Initial steam shortcut failed to start the program
  • Recovery partition failed to install and wouldn't shut down properly
  • SteamOS cannot be used with more than 1 monitor!
  • Upon login, steam requires a confirmation code. That's sent to your e-mail. Which you need a web browser for.
  • Steam doesn't have any default repositories
  • Sound doesn't work

To install SteamOS, I essentially followed the steps outlined here, but they weren't all nicely organized for me. I downloaded the zip, extracted it into a FAT32 usb, copied the syslinux files, executed syslinux on the drive, and wrote syslinux.cfg, which is improperly formatted in that post. Here is the proper formatting:

DEFAULT linux
TIMEOUT 50
LABEL linux
    kernel install.amd/vmlinuz
    append initrd=install.amd/gtk/initrd.gz preseed/file=/cdrom/default.preseed DEBCONF_DEBUG=developer desktop=steamos auto=true priority=critical video=vesa:ywrap,mtrr vga=788 -- quiet

At this point I had done everything I needed to do from windows. SteamOS cannot be dual-booted, because it obliterates whatever drives are connected to the computer. To work around this, I used a second hard drive and disconnected the first one. To avoid any mistakes, I physically disconnected the drive from the computer to ensure it would be safe. Only after doing that and disabling it in the BIOS did I configure the USB to boot up.

WARNING: DO NOT CONFIGURE YOUR BIOS TO BOOT FROM USB UNTIL ALL OTHER HARD DISKS HAVE BEEN REMOVED FROM YOUR SYSTEM. THERE IS NO CONFIRMATION DIALOG. THERE IS NO BUTTON THAT SAYS "PRESS OK TO IRREVERSIBLY DESTROY ABSOLUTELY EVERYTHING ON THIS SYSTEM." THE MOMENT IT BOOTS OFF THAT USB, ANYTHING CONNECTED TO THE COMPUTER WILL BE DESTROYED.

As expected, the installer failed when installing grub. I dropped into the terminal and typed in the magic instructions, which were a lot easier to do after I realized I could just hit tab and have the terminal complete the filenames for me. Once I got back into the setup, though, the guide didn't mention that you actually have to hit continue 3 or 4 times. However, it did indeed work on the second try, and I soon found myself booting into a GNOME environment.

It's important that, when first logging in, you pick the GNOME shell environment. It isn't the default, and it's not the SteamOS environment. Failure to do so will fuck everything up really bad. However, once I did get into the GNOME shell environment, the steam shortcut didn't work. I don't know why, but I had to go into the terminal and manually execute /usr/bin/steam %U. This is exactly what the shortcut did, but for some reason it only worked when I typed it into the terminal. Once steam was installed, I logged off and logged into the desktop account (password: desktop). I was able to run ~/post_logon.sh without a hitch, and the system rebooted.

Then, the recovery creator failed. It failed spectacularly. It spat out a bunch of errors, tried to continue, then dropped into a terminal. I told it to restart, but it failed. It kept reverting back to the terminal because it somehow couldn't disconnect the terminal session despite me telling it to shut-the-fuck-down-right-now-or-else. So I just held the power button down and did a hard shutdown. Once I rebooted, despite not having a recovery partition, it seemed to work just fine. It booted into steamOS and then...

Nothing. Black screen. Complete failure.

This, however, turns out to simply be what happens when Steam's compositor encounters two monitors. Instead of shutting one off, it just completely dies. After unplugging my second monitor, steam worked like a charm, and I logged in, and then... I was prompted to enter a confirmation code sent to my e-mail. Which I needed a web browser to get to, which required that I logged in. Thankfully, I had a laptop sitting next to me, so this wasn't a problem, but fair warning to anyone else who's logging in.

Now I was in the Steam client, but I had no sound. Dropping back to desktop was easy after checking the "Enable Linux Desktop" option under "Interface", but I had to assign a new password while in desktop mode so I could use sudo (this is done using the passwd command).

The problem is that steam's only default repository is for, well, steam. To get anything else that would make my OS usable, like have sound, I needed to add back in the default debian repositories. SteamOS thankfully ships with nano, so I typed sudo nano /etc/apt/sources.list and added the following:
deb http://http.debian.net/debian wheezy main
deb-src http://http.debian.net/debian wheezy main

Now, after running sudo apt-get update, I had access to the default packages, which crucially included ALSA, the linux audio API and low-level driver package. After installing and restarting ALSA, however, I still didn't have sound. Sometimes when this occurs, it's recommended to open a console and run rm -rf ~/.pulse to delete the .pulse configuration files, which can mess things up. In my case, however, the hardware still wasn't being detected. To solve this, I installed alsa-firmware-loaders. After rebooting, my sound still didn't work, so I ran alsa force-reload. This finally did the trick, and I had sound on the desktop! But, not on the steam client, or the games.

Rebooting finally graced me with sound in the steam client, but disabled sound on the desktop. So, now I have sound on Steam, but not on the desktop. This isn't a big problem right now, but hopefully someone can fix it eventually.

Unfortunately, I could not get flash working, and debian comes with a firefox fork, which doesn't support whatever audio API everyone wants to use right now. Luckily, now that we have the default debian packages, we can install things like GNOME tweaker, and other fun things to customize our steamOS experience.

Once I got sound working, I tried out a few games. SpaceChem did not appear to have a fully-working linux client, because it failed to sync my saves from steam cloud, and half it's menu buttons were just gone. Team Fortress 2 worked fine, aside from awkward looking text, but it was running at about 2 FPS until I disabled motion blur. After doing that, it abruptly started running smoothly, with just a few hiccups here and there, so I don't know what that was about.

My computer only has 4 GB of RAM, so TF2 normally has memory issues on windows, which usually cause temporary freezeups. On steamOS, those memory problems still exist, but instead of causing temporary freezeups, the entire game instantly crashes. Given that this is a failure case, it's not really something I'm allowed to complain about, but be warned: don't run out of RAM.

Aside from the occasional whacky interface, playing games on SteamOS feels almost identical to playing them on windows. Performance and load times appear to be identical to windows, controls are responsive, everything usually works. While this is only a beta, I consider this a step in the right direction, and am optimistic about the future of SteamOS.

December 2, 2013

Tile-Based Discrete Wavefront Propagation

I'm currently building a very simplistic first-person shooter in WebGL. An example of this algorithm, with the debug code left in, is available here. The map is represented by a grid - a cell is solid if its 0, and empty if its 1. This is trivial to render by using a standard recursive 4-direction flood fill algorithm. Unfortunately, we can't simply render the entire level if our rooms contain high levels of detail or many objects, because we'll overload the GPU.

Frustum culling is the obvious answer, but I need it to be highly efficient. This means adjusting the frustum to account for corners, so I only render the visible portions of the level. While a lot of the speed concerns I currently have can be alleviated using batch rendering, this will stop working the instant I put in details that can't be batch rendered. Consequently, I want the algorithm to be as close to perfect as possible, only rendering rooms that are visible and no others.

This is where Tile-Based Discrete Wavefront Propagation comes in. The central idea is to represent the viewing frustum as a wave that flows through the level, getting split up when it hits corners. If properly implemented, this will be exact, only rendering rooms that are visible and no others. It turns out that you can implement this in $$O(n)$$ time, but we can't use the naïve recursive flood-fill anymore, because it's depth first. If we want to simulate a wave, we need to render the grid using a breadth-first search, to simulate it slowly spreading outward. Breadth first search is implemented using a queue by simply pushing all neighboring nodes on to the queue and rendering them until the queue is empty.

As the wave propagates through the level, we adjust the left and right angles of each individual wavefront according to the walls that we hit. This requires that we deal with two possible cases: the case where a wall is in front of the wave as it propagates through the level, and the case where it isn't. The only time the wave can actually be split up is when a wall is in front of it - the rest of the time, it is simply clipped on the sides. "Front" and "side" are defined based on what direction the wave came from.

Starting with the case where there isn't a wall in front, we check to see if there is a wall on the right. If there is, we check the angles of it's corners. If either angle is inside the culling frustum, we change the right-angle to the one that is "farthest inside" (done in code by simply checking each angle one after the other). Then we do the same for the left wall, this time changing the left-angle, if appropriate. Then we send the updated angles to the neighboring tiles - the left one gets (left-angle,new-right-angle), the front gets (new-left-angle,new-right-angle), and the right gets (new-left-angle,right-angle).

If there is a wall in front, everything stays the same (note that the front wall has it's own set of corners you must check), but the angles that get sent through the neighboring tiles change. The left wall gets (left-angle,new-left-angle), the front doesn't exist so we ignore it, and the right wall gets (new-right-angle,right-angle). This effectively splits the wave down the middle, but it makes things complicated. Before, if a new left-angle was outside the culling frustum, we would just set it to the old left-angle. This doesn't work anymore, because we're splitting the wave, which means we require a new left-angle that isn't equal to the old left-angle. To solve this, if the new left-angle fails to exist, we set it to the old right-angle instead of the old left-angle, and vice-versa for the new right-angle.

Conceptually, this isn't too complicated, but the actual implementation gets complicated very fast due to angles being a giant pain in the ass to work with. We have to seed the initial queue with the neighboring tiles, and deal with getting proper frustum culling working, which is far more difficult than it seems. This will require a sizable number of utility functions, so we'll look at those first:

function realmod(i,m) { i=(i%m); return i+((i<0)*m); } // Mathematically correct modulo
// Queue implementation using a circular array. Resize is very expensive, but almost never happens, because it remembers its size after each frame.
function Queue(sz) {
  this.array = new Array(!sz?1:sz);
  this.cur=-1;
  this.length=0;
  this.push = function() {
    for (var i = 0; i < arguments.length; i++) {
      if(this.length>=this.array.length) {
        this.resize(this.array.length*2);
      }
      this.cur=((this.cur+1)%this.array.length);
      this.array[this.cur] = arguments[i];
      this.length += 1;
    }
  }
  this.pop = function() { return this.get(--this.length); }
  this.peek = function() { return this.get(this.length-1); }
  this.get = function(i) { return this.array[this.modindex(i)]; }
  this.clear = function() { this.cur=-1; this.length=0; }
  this.resize = function(nsize) { 
    var sz=this.array.length;
    var c = this.cur+1;
    for(var i=sz-c; (i--)>0;) {
      this.array[c+nsize-sz+i]=this.array[c+i];
    }
  }
  this.modindex = function(i) { return realmod(this.cur-i,this.array.length); }
}
function realfmod(x,m) { return x - Math.floor(x/m)*m } // Implements mathematically correct fmod
// Gets absolute distance between two angles
function getAngleDist(u,v) { return Math.PI - Math.abs((Math.abs(u - v)%(Math.PI*2)) - Math.PI); } 
// Gets the signed distance between two angles
function getAngleDistSign(u,v) { return ((realfmod(v - u,Math.PI*2) + Math.PI)%(Math.PI*2)) - Math.PI; } 

  function getdx(dir) { dir=((dir+4)%4); return (dir==0)-(dir==2); }
  function getdy(dir) { dir=((dir+4)%4); return (dir==1)-(dir==3); }
  function exists(x,y,m,w) { var i = x + (y*w); return x>=0 && x<w && i<m.length && (m[i]&1)!=0; }
  function exists_dir(x,y,m,w,dir) { return exists(x+getdx(dir),y+getdy(dir),m,w); }

  // Gets the angle of a point from the player's origin (which is the camera's origin)
  var getangle = function(x,y) { return Math.atan2(y-player[0].elements[2],x-player[0].elements[0]); }
  // Gets the angle of a corner, offset from the given point by dir and diri.
  var getangle_dir = function(x,y,dir,diri) { return getangle(x+getdx(dir)*5 + getdx(diri)*5,y+getdy(dir)*5 + getdy(diri)*5); }

First, the modulo operators in most programming languages are actually remainder operators. They do not perform mathematically correct modulo, and their behavior when you feed them negative numbers is not what you'd expect. The first thing we do, then, is define a modulo function that actually behaves like the modulo operator. We then use this to build a circular queue that resizes itself when necessary. When resizing, the queue must move all items to the right of the index over, which is a costly operation, so we let it keep it's size across frames. This makes the number of resize operations essentially zero.

The next few functions deal with angles. Angles are inherently circular, and this causes all sorts of problems. If our left-angle is 355°, and our right angle is 5°, the distance between these two angles is 10°, not 350°. There is a standard method to getting the absolute distance between two angles using the floating point modulo operator, which is implemented in getAngleDist(). This is all well and good, but we have defined left and right angles, which means we need to know if something is on the left hand side, or the right hand side. This requires a signed angular distance function, which makes things much more complicated because, once again, the floating point modulo operator is not actually modulo, it's a remainder.

So, we need to implement a proper floating point modulo operator. The standard fmod() function is implemented using the following formula:\[ \DeclareMathOperator{\fmod}{fmod} \DeclareMathOperator{\trunc}{trunc} \fmod(n,d) = n- \trunc\left(\frac{n}{d}\right) d\]It's trivial to change this formula into one that gives us the correct behavior (remember, truncation is not flooring!):
\[ \fmod(n,d) = n- \left\lfloor\frac{n}{d}\right\rfloor d\]We can use this to define a function such that, as long as $$b-a$$, when forced into the range $$\left[0,2\pi\right)$$, is less than $$\pi$$ (or 180°), we get a positive distance. If it goes past $$\pi$$, it becomes negative and heads back towards 0, just like in the absolute value distance function, but now with the proper sign. We will use this later to determine if a tile crosses over our angular culling frustum. getdx(),getdy(),exists(), and exists_dir() are all used to either bump x/y coordinates according to a direction, or determine if a specific tile exists. Now we get to the real function:

var roomq = new Queue(10); // queue holding nodes
var drawmap = function(x,y,m,w,langle,rangle) { // map drawing function
  var i = x + (y*w);
  m[i]=(m[i]|2);
  // draw floor
     
  for(var j = 0; j < 4; ++j) { // Push initial neighbors on to the queue
    var nx=x+getdx(j);
    var ny=y+getdy(j);
    if(!exists(nx,ny,m,w)) { // If it doesn't exist, we ran off the edge of the map or hit a wall
      // draw wall
    } else {
      roomq.push(nx,ny,langle,rangle,j);
    }
  }
  
  var dir=0; // Stores the direction the wave is going. 0: (+) x-axis, 1: (+) y-axis, 2: (-) x-axis, 3: (-) y-axis
  while(roomq.length>0) {
    x = roomq.pop();
    y = roomq.pop();
    langle = roomq.pop();
    rangle = roomq.pop();
    dir = roomq.pop();
    var i = x + (y*w);
    var room=m[i];
    if((room&2)==2) continue; // If true, we already visited this node
    var mid = [langle,getAngleDistSign(langle,rangle)/2];
    if(mid[1]<0) continue; // If this is less than 0, langle has cross over rangle, so there's nothing to render.
    mid[0]=langle+mid[1];
    var angles=[getAngleDistSign(getangle(x*10+5,y*10+5),mid[0]),
                getAngleDistSign(getangle(x*10-5,y*10-5),mid[0]),
                getAngleDistSign(getangle(x*10-5,y*10+5),mid[0]),
                getAngleDistSign(getangle(x*10+5,y*10-5),mid[0])];
    if(angles[0]>mid[1] && angles[1]>mid[1] && angles[2]>mid[1] && angles[3]>mid[1]) continue;
    if(angles[0]<-mid[1] && angles[1]<-mid[1] && angles[2]<-mid[1] && angles[3]<-mid[1]) continue;
    if(Math.abs(angles[0])>Math.PI/2 && Math.abs(angles[1])>Math.PI/2 && Math.abs(angles[2])>Math.PI/2 && Math.abs(angles[3])>Math.PI/2) continue;
    m[i]=(m[i]|2); // Only mark as done if we actually render it. This let's us recover from inconsistencies.
    // Draw floor
    var nlangle=langle;
    var nrangle=rangle;
    var front = exists_dir(x,y,m,w,dir); // Is there a wall in front of us?
    var lwall = exists_dir(x,y,m,w,dir-1); // To the left?
    var rwall = exists_dir(x,y,m,w,dir+1); // To the right?
    
    if(!front || !lwall) { //left wall or front wall check
      nlangle=getangle_dir(x*10,y*10,dir,dir-1);
      if(getAngleDist(mid[0],nlangle)>mid[1]) nlangle=(!front)?rangle:langle; 
    }
    if(!lwall) { // This corner is only checked for left walls
      nlangle=getangle_dir(x*10,y*10,dir-2,dir-1);
      if(getAngleDist(mid[0],nlangle)>mid[1]) nlangle=langle; 
    }
    if(!front || !rwall) { //right wall or front wall check
      nrangle=getangle_dir(x*10,y*10,dir,dir+1);
      if(getAngleDist(mid[0],nrangle)>mid[1]) nrangle=(!front)?langle:rangle;
    }
    if(!rwall) { // Only right wall
      nrangle=getangle_dir(x*10,y*10,dir-2,dir+1);
      if(getAngleDist(mid[0],nrangle)>mid[1]) nrangle=rangle;
    }
    
    for(var j = dir-1; j <= dir+1; ++j) {
      var k = (j+4)%4; // get proper direction
      var nx=x+getdx(k);
      var ny=y+getdy(k);
      if(!exists(nx,ny,m,w)) { // We ran off the edge of the map or hit a nonexistent block
        // Draw wall
      } else {
        if(j==dir-1) { roomq.push(nx,ny,langle,(!front)?nlangle:nrangle,k); }
        else if(j==dir) { roomq.push(nx,ny,nlangle,nrangle,k); }
        else { roomq.push(nx,ny,(!front)?nrangle:nlangle,rangle,k); }
      }
    }      
  }
}
var reversefill = function(x,y,m,w) {
  var i = x + (y*w);
  if(x<0 || x>=w || i>=m.length) return;
  if((m[i]&2)==2)
  {
    m[i]=(m[i]&(~2));
    reversefill(x+1,y,m,w);
    reversefill(x,y+1,m,w);
    reversefill(x-1,y,m,w);
    reversefill(x,y-1,m,w);
  }
}

Straddle Error
First, we push our 4 neighboring tiles, provided they exist, on to the queue, seeding them with appropriate directions that radiate outward from our starting point. Then, we start running through the queue, and do an initial check to see if we already dealt with this tile. If not, we check to make sure that the left-angle is really less than the right-angle, and then go into standard frustum culling. In order to figure out if a tile is within our view, we need to ensure that the entire tile is either to the right or to the left of our angular viewing frustum. This means that all 4 corners must have angles outside of our frustum, and they must all be on the same side. If they are not on the same side, then the cone could have passed through the center.

This is what the first two if statements do. The problem is that a tile directly behind us will also be considered straddling the angular range, because our distance function wraps at 180°. To solve this, we have a third if statement that throws away everything that is more than 90° (or $$\frac{\pi}{2}$$) from the center of our frustum. This means the maximum horizontal field-of-view is 180°. Note that this culling is independent of the algorithm, you'd be using this same logic if you were only doing simple frustum culling.


Split Error
If the tile survived the culling function, we mark it as visited. It's important that we only mark a node as visited after we have decided to render it because of a very nasty edge-case that can happen during the breadth-first traversal. It's possible for a tile that is rendered on one side of a split frustum to reach a visible tile on the other side of the split, and erronously mark it as invisible, using it's own frustum. The tile actually is visible, but only to the frustum on the other side of the split.

Then, we check the appropriate corners and assign langle and rangle appropriately. The neighbors are iterated and new values passed as needed. Once this phase of the algorithm is completed, we call reversefill(), starting on the same tile we called drawmap() with. This will use the standard fill algorithm to reset the "visited" marks on the map. By doing this, we avoid having to set all 2500 nodes of a 50x50 map to 0. The algorithm is now complete.

Because this algorithm runs in $$O(n)$$ time and is exact, it is asymptotically optimal. The problem is that it is only optimal in a single-threaded sense. The breadth-first iteration technique allows us to run each individual level concurrently, but this will only reduce the worst-case complexity from $$O(mn)$$ to $$O(\max(m,n))$$. 50 is a lot better than 2500, but this is only for a very, very large room. If we're dealing with a hallway, the concurrent performance would be identical to the single-threaded performance!

Consequently, while this is useful for tight corridors, the algorithm itself isn't really that useful outside of the game's narrow domain. Once the rooms start getting large enough, you're probably better off brute-forcing most of it and using approximations. However, the algorithm is exact, which is very important for calculating Enemy Line-of-Sight. So if you're dealing with a grid-based game and need to figure out if an enemy has a direct line of sight, this technique allows you to make a precise calculation, since it only hits tiles that are visible, and no others. This gives it an advantage over naïve raytracing, which requires many rays and is prone to giving false-negatives when dealing with narrow hallways.

Unfortunately, it still breaks when you try to make it work with FoV's greater than 180°, so unless you split them up into 90° chunks, it's pretty useless for things like lighting. I'm probably not the first to come up with the algorithm, either; someone probably invented this in their garage in 1982. Oh well.

November 17, 2013

Google's Decline Really Bugs Me

Google is going down the drain.

That isn't to say they aren't fantastically successful. They are. I still use their products, mostly because I don't put things on the internet I don't want other people to find, and I'm not female, so I don't have to worry about misogynists stalking me. They still make stupendous amounts of money and pump out some genuinely good software. They still have the best search engine. Like Microsoft, they'll be a force to be reckoned with for many decades to come.

Google, however, represented an ideal. They founded the company with the motto "Don't Be Evil", and the unspoken question was, how long would this last? The answer, oddly enough, was "until Larry Page took over".

In its early years, Google unleashed the creativity of the brilliant people it hired to the world and came up with a slew of fantastic products that were a joy to use. Google made huge contributions to the open-source world and solved scalability problems with an elegance that has yet to be surpassed. They famously let engineers use 20% of their time to pursue their own interests, and the result was an unstoppable tidal wave of innovation. Google was, for a brief moment, a shining beacon of hope, a force of good in a bleak world of corporations only concerned with maximizing profit.

Then Larry Page became CEO. Larry Page worshiped Steve Jobs, who gave him a bunch of bad advice centered around maximizing profit. The result was predictable and catastrophic, as the entire basis of what had made Google so innovative was destroyed for the sake of maximizing profit. Now it's just another large company - only concerned about maximizing profit.

Google was a company that, for a time, I loved. To me, they represented the antithesis of Microsoft, a rebellion against a poisonous corporate culture dominated by profiteering that had no regard for its users. Google was just a bunch of really smart people trying to make the world a better place, and for a precious few years, they succeeded - until it all came tumbling down. Like an artist whose idol has become embroiled in a drug abuse scandal, I have lost my guiding light.

Google was largely the reason I wanted to start my own company, even if college kept me from doing so. As startup culture continued to suck the life out of silicon valley, I held on to Google as an ideal, an example of the kind of company I wanted to build instead of a site designed to sort cat photos. A company that made money because it solved real problems better than everyone else. A company that respected good programming practices, using the right tool for the job, and the value of actually solving a problem instead of just throwing more code at it.

Google was a company that solved problems first, and made money second.

Now, it has succumbed to maximizing stock price for a bunch of rich wall street investors who don't care about anything other than filling their own pockets with as much cash as they possibly can. Once again, the rest of the world is forced to sit around, waiting until an investor accidentally makes the world a better place in the process of trying to make as much money as possible.

Most people think this is the only way to get things done. For a precious few years, I could point to Google and say otherwise. Now, it has collapsed, and its collapse has made me doubt my own resolve. If Google, of all companies, couldn't maintain that idealistic vision, was it even possible?

Google gave me a reason to believe that humanity could do better. That we could move past a Wall Street that has become nothing more than a rotting cesspool of greed and corruption.

Now, Google has fallen, along with the ideal it encompassed. Is there a light at the end of the tunnel? Or is it a train, a force of reality come to remind us that no matter how much we reach for utopia, we will be sentenced to drown in our own greed?

October 29, 2013

The Educational Imbroglio

im·bro·glio
noun
1. an extremely confused, complicated, or embarrassing situation.

Across the country, there is a heated debate over our educational system. Unfortunately, it's a lot like watching members of the flat earth society argue about whose theory is right - there is no right answer, because everyone is wrong.

The most recent and perhaps egregious example of this is a breathtakingly misguided article by Kevin G. Welner, who is the director of the National Education Policy center, which is absolutely terrifying. He is attempting to discredit the idea of "tracking", wherein low-performing students are separated from higher achieving students, because obviously you can't teach kids who "get it" the same way as kids who are struggling. Unfortunately, the entire conclusion rests on a logical fallacy. He says, and I quote:
"When children fall behind academically, we have a choice. We can choose to sort them into less demanding classes where they will fall further behind, or we can choose to include them in classes that maintain high expectations."
This is a false dichotomy, since there are many other choices. We can sort them into a class with the same expectations, but an alternative teaching method. Sort them into a class that actually pays attention to the concepts that are giving them trouble. The idea is to help children who have fallen behind catch up with their peers, not throw them in a room and forget about them. Schools that simply lower their expectations of poorly performing students are doing it wrong. Furthermore, trying to argue that something can't work because no one's doing it properly is another logical fallacy.

There's also a persistent argument against charter schools, which claims that the money spent on charter schools should instead be used to improve public schools instead. This is laughable, because public schools receive funding based on test scores. So, all the money would be spent improving test scores instead of actually teaching children anything. Charter schools are important because they aren't bounded by these nonsensical restrictions and thus are free to experiment with alternative teaching styles. Throwing money at our public schools will only shore up a method of teaching that's fundamentally broken. It's like trying to fix the plumbing after the roof caved in - it's completely missing the point.

To make matters worse, there's also a war on free time. Recess is being cut in favor of increased instruction time, while educators cite minuscule increases in test scores as proof that this "works". If by "works", you mean it succeeds in cramming more useless junk into kids heads, then sure, it's "working". However, if you want kids to actually learn instead of memorize pointless facts that they will immediately forget, you have to give them time to process concepts. Their brains need rest, not more work. Bodybuilders don't lift weights as long as they can every single day; they lift weights every other day and only for a few hours or so, because the muscle needs time to recover.

This, however, is an issue with a society that thinks hard work means working yourself to exhaustion. This is incredibly short-sighted and in direct opposition to plenty of evidence that points to rest being a necessary part of a healthy lifestyle. It can be your job, or school, or a hobby, it doesn't matter. Humans do not function effectively when forced to focus on one thing for hours at a time. The only reason we attempt to do this is because we used to work in factories, but nowadays we have robots. Modern jobs are all about thinking creatively, which cannot be forced. You can't force yourself to understand a concept. It's like trying to force a broken leg to heal faster by going for a jog. You must give kids time absorb concepts instead of trying to cram it down their throats. They need to understand what they are learning, not memorize formulas.

Mainstream education doesn't take this seriously. There are plenty of experiments that have effectively taught children advanced concepts with radically different teaching methods. One guy taught 3rd graders binary. These kids learned english and how to operate a computer without a teacher at all. There are plenty of cases that show just how woefully inadequate our teaching system is, but it seems that we care more about a one-size-fits-all method that can be mass-produced than a method that's actually effective.

Our educational system is failing our students, and we refuse to even entertain notions that could make a difference. Instead, we just legislate more tests and take away their recess.

Because really, memorizing the date of the Battle of Gettysburg is more important than playing outside and having a childhood.

October 3, 2013

The Ladder-Climbing Generation

Creating a life that reflects your values and satisfies your soul is a rare achievement. In a culture that relentlessly promotes avarice and excess as the good life, a person happy doing his own work is usually considered an eccentric, if not a subversive. Ambition is only understood if it's to rise to the top of some imaginary ladder of success. Someone who takes an undemanding job because it affords him the time to pursue other interests and activities is considered a flake. A person who abandons a career in order to stay home and raise children is considered not to be living up to his potential - as if a job title and salary are the sole measure of human worth. You'll be told in a hundred ways, some subtle and some not, to keep climbing, and never be satisfied with where you are, who you are, and what you're doing. There are a million ways to sell yourself out, and I guarantee you'll hear about them.

To invent your own life's meaning is not easy, but it's still allowed, and I think you'll be happier for the trouble.


  — Bill Watterson, 1990 speech at Kenyon College

Someone, once again, is complaining about those misbehaving youngsters who don't understand the value of hard work. He lampoons the advice to follow your passion, saying that young people are just scared of hard work. He makes the dangerously misinformed claim that burn-out is just a myth: "Burn out is just a rationalization for giving up early."

For someone who seems so sure of what they're talking about, it would be difficult for him to be more wrong. Following your passion doesn't mean you do less work. It doesn't even mean you'll avoid doing boring things. A standard 9-5 job doesn't require you to think. You drive to work, get told what to do by some guy in a suit for 8 hours, then go home. It's about following instructions, not actually doing anything difficult. Most programmers are lucky, and have plenty of employers who give them interesting problems to work on. In fact, for calling his post "The Hacker News Generation", he doesn't seem to understand his audience very well. One of the current talking points is startups overworking their employees by expecting 80 hour work weeks, and how employees are trained to think this is ok.

That kind of seems like the exact opposite of an aversion to hard work.

Following your passion is immeasurably more difficult than climbing a corporate ladder. You usually work more hours for less pay, and often have to struggle to make ends meet. You have to do every part of your job, including all the mind-numbingly boring stuff, because there isn't anyone else to do it. People who are following their passion enjoy it more because they're doing something that's important to them, not because they're doing less work. An artist is the one drawing constantly, every day, barely making enough money to feed themselves. The guy at Microsoft writes a bunch of test code, checks it in, then gets lunch at the cafeteria. Where does this glorification of doing boring, repetitive tasks come from?

These people are busy climbing a ladder that society has put in front of them. They look out and see someone running around on the ground, away from the ladder, and become convinced they are hopelessly lost. Clearly, they don't understand the value of ladder climbing. When they realize that other people don't care about the ladder, they immediately conclude that these people don't understand what's important, because the only success they know of is the success they were promised by society at the top of the ladder.

A human being's worth cannot be measured in dollars or promotions. To follow one's dreams is not an act of cowardice, but rather one of incredible courage. To resist taking the easy way out, to avoid the routine of a 9-5 job, is to accept a life that is often filled with failure and hardship. The difference is that it will be a life worth living.

September 18, 2013

The Microsoft Word Problem

I use FL Studio 11 to make my music. Some people find this surprising, due to FL Studio's stigma as being a "toy" DAW that it simply cannot seem to shake, despite the fact it actually does most things as well or better than other professional DAWs. FL Studio has two real, significant issues: Large projects are unstable, and it has extremely bad 64-bit support.

This is almost never what people actually complain about. Instead, people complain about FL studio lacking features when they really just need to enable the right option. My friend lamented FL Studio's poor handling of automation clips without knowing about the "browse parameters" feature that lists all of a synth's parameters and highlights the one you are changing. He then complained that it didn't play notes when you started playback in the middle of them - this can be toggled in the audio settings. He also didn't know how to group multiple instruments to be controlled by the same piano roll, so I had to show him how to use Layers. Every single reason he gave for FL Studio being crap was just him not understanding how to use it properly, or not knowing where to find a specific feature.

This is the exact same problem Microsoft had with Word, and it's what resulted in the Ribbon GUI overhaul. Every reason people gave for not liking Word was just a result of them not being able to find the feature they wanted in an endless cascade of menus. To address this, it required a GUI overhaul so those features were grouped in intuitive ways, so people could find them more easily.

Even APIs can suffer from the Microsoft Word Problem. OpenGL, especially it's early incarnations, was essentially a giant, opaque list of functions that randomly referenced each other and had no clear organization. The online documentation is literally just an alphabetized list of every single OpenGL function in existence. The end result is that you need to know precisely what you want to do in order to find the right function. This is in contrast to DirectX, which (for example) has every single renderstate in a single, enormous enumerator. That enumerator contains something like 50 or so equivalent OpenGL function calls, which are not grouped in any meaningful way. It's documentation, like everything else on MSDN, is organized in hierarchical groups. DirectX tells you every single possible thing you theoretically might be able to do with your graphics card. OpenGL, on the other hand, has extensions, which are both a blessing and a curse. It makes OpenGL inherently more adaptable than DirectX, but at the cost of having absolutely no idea what the graphics card may or may not be capable of, because it's just not in OpenGL, it's in some extension you have to dig up.

Just like Microsoft Word, the features are all there in OpenGL, they're just harder to get to. And you'd better hope you know exactly what your technique is called, or you'll never find the function you want. WebGL inherits this problem, and throws on a few of its own inherent with attempting to bolt a low-level C api on to a high level web language that needs to be sandboxed.

We can't simply implement a feature, we have to make it easy to find, and easy to use, or it's worthless. It's amazing how quickly programmers forget the importance of context. In all of these cases, the solution to feature overload is conceptually very similar - Word created the Ribbon, which grouped related features under tabs and sub-groups. A similar grouping of OpenGL functions and parameters would do wonders for it's usability. FL Studio would also benefit by dumping it's left-hand browsing bar in favor of a Ribbon or module approach that didn't force 15 wildly different GUI styles into a single menu.

Context is important. If I want to find the function that sets the alpha blending operation in OpenGL, I should not have to go through over 300 functions to find it. I should be able to go to the "sampling" functions and look in the "blending" subgroup, and poof, all the functions that have anything to do with blending are there. It doesn't matter if we're designing word processors, digital audio workstations, low level APIs, middleware, or web applications. Anything and everything is susceptible to the Microsoft Word Problem.

September 12, 2013

Write Less Code

"Everything should be as simple as possible, but not simpler." - Albert Einstein (paraphrased)
The burgeoning complexity of software is perhaps one of the most persistent problems plaguing computer science. We have tried many, many ways of managing this complexity: inventing new languages, creating management systems, and enforcing coding styles. They have all proven to be nothing more than stopgaps. With the revelation that the NSA is utilizing the inherent complexity of software systems to sabotage our efforts at securing our systems, this problem has become even more urgent.

It's easy to solve a problem with a lot of code - it's hard to solve a problem with a little code. Since most businesses do not understand the advantage of having high quality software, the most popular method of managing complexity is not to reduce how much code is used, but to wrap it up in a self-contained library so we can ignore it, instead. The problem with this approach is that you haven't gotten rid of the code. It's still there, it's just easier to ignore.

Until it breaks, that is. After we have wrapped complex systems into easy-to-use APIs, we then build even more complex systems on top of them, creating networks of interconnected components, each one encapsulating it's own complex system. Instead of addressing this burgeoning complexity, we simply wrap it into another API and pave over it, much like one would pave over a landfill. When it finally breaks, we have to extract a core sample just to get an idea of what might be going wrong.

One of the greatest contributions functional programming has made is its concept of a pure function with no side-effects. When a function has side effects, it's another edge on the graph of components where something could go wrong. Unfortunately, this isn't enough. If you simply replace a large complex system with a bunch of large complex functions that technically have no side-effects, it's still a large complex system.

Object-oriented programming tries to manage complexity by compartmentalizing things and (in theory) limiting how they interact with each other. This is designed to address spaghetti code that has a bunch of inter-dependent functions that are impossible to effectively debug. The OO paradigm has the right idea: "an object should do exactly one thing, and do it well", but suffers from over-application. OO programming was designed to manage very large complex objects, not concepts that don't need Get/Set functions for every class member. Writing these functions just in case you need them in the future is a case of future-proofing, which should almost always be avoided. If there's an elegant, simple way to express a solution that only works given the constraints you currently have, USE IT. We don't need any more leaning towers of inheritance.

The number of bugs in a software program is proportional to how much code you write, and that doesn't include cheap tricks like the ternary operator or importing a bunch of huge libraries. The logic is still there, the complexity is still there, and it will still break in mysterious ways. In order to reduce the complexity in our software, it has to do less stuff. The less code you write, the harder it is for the NSA to sabotage your program without anyone noticing. The less code you write, the fewer points of failure your program will have. The less code you write, the less stuff will break. We cannot hide from complexity any longer; we must actively reduce it. We have to begin excavating the landfill instead of paving over it.

September 2, 2013

Most People Have Shitty Computers

Premature optimization is the root of all evil - Donald Knuth
Ever since I started putting words on the internet, I have complained about the misinterpretation and overgeneralization of this Donald Knuth quote. Developers essentially use it as an excuse to never optimize anything, because they can always say they "aren't done yet" and then permanently render all optimizations as premature. The fact that "premature" is inherently a subjective term doesn't help. The quote was meant to target very low-level optimizations that are largely useless until you're positive everything else is working properly and you have no other low-hanging fruit to optimize.

Instead of following that advice, and only doing complex optimizations after all the low-hanging fruit has been picked, developers tend to just stop optimizing after the low-hanging fruit is gone. Modern developers will sometimes stop optimizing things entirely and leave it up to the compiler, which almost always does a horrible job at it. Because web development is inherently dependent on one of the worst programming languages currently being used by anyone, these issues are even more prominent.

When people complain about stuff not working on their phones while on shitty internet connections (which is every single free wifi hotspot ever), the developers tell them to stop using shitty internet connections. When they complain about how slow and unresponsive a stupid, unnecessary app whose entire purpose is to just display text (I'm looking at you, Blogger), the developers tell them to get a better phone. When someone writes an app that doesn't compress anything and sucks up bandwidth like a pig, for absolutely no reason at all, the developers tell them to get a better data plan.

What the fuck?

Just because you have a desktop with an 8-core processor and 32 gigs of RAM doesn't mean your customers do. The number of people using the top-of-the-line technology is a tiny fraction of the total number of people who actually use the internet, which at this point is more than 1/3 the population of the entire human race. Only targeting hipster white kids who live in San Francisco and have rich parents may work for a small startup, but when Google's mail app turns into a piece of sludge that moves about as fast as pitch at room temperature, we have crossed a line. Google is everywhere. Their stuff should work well on the shittiest internet connection you can imagine. You can't go around expecting all your customers to have perfect internet all the time when it's just not possible.

Don't just target the latest version of Windows and tell the other versions to stuff it, because it's almost never really necessary when all you're doing is using 3 or 4 new functions introduced in Windows 7 that could easily be encapsulated in a small check. Don't write your game in such a way that it will only be playable on a high end gaming machine because you will get a lot of flak. If making this happen is hard, you probably have a shitty game engine that has a bad architecture. Likewise, when my orchestral VSTi sucks up 10% of my CPU while it's just sitting there and NOT ACTUALLY DOING ANYTHING, something is seriously wrong. I know it's using the exact same sample format as Kontact (someone reverse-engineered it), except that it does everything 4 times slower. Yet, when people complain, and they complain all the time, the response is always "you need a better computer."

Most people have shitty computers. Your customers don't care about all the cool new features you can implement for your mail app now that you have time to work on them because you never bothered to optimize it properly - they just want a mail app that WORKS.

July 23, 2013

Leap Motion Impressions, Input Sanitation, and 3D Gesture Ideas

Pros:
  • For the most part, does what it claims it does, and gives you extremely precise, fast tracking of fingers.
Cons:
  • Really hates thumbs for some reason.
  • Has a lot of trouble with pens or other implements.
  • Fingers must be separated.
  • Fairly easy to get positions that break the camera because it can't see the fingers.
  • No one has any idea how to write software for it.

I just got my Leap Motion device today, and for the most part, I like it. It does most of the things I expected it to do. It seems like something that could become very useful down the line. Unfortunately, right now, I wouldn't recommend getting one if you wanted something that's more than a toy.

This isn't entirely the fault of the device itself, but more a combination of driver limitations and boneheaded software that doesn't know what it's doing. The device is so new, no one knows how to properly utilize it, so almost all the apps that exist right now are either garbage or ridiculously sensitive to your setup. There are, however, a few more serious problems that should be addressed by the Leap Motion team.

First of all, the driver hates thumbs. It seems like it's trying to edit them out when they aren't positioned like a finger, which makes any sort of pinching gesture impossible to do. In addition, it doesn't like it when you try to use a pen, despite the fact that it's specifically designed to let you do so. Both of these problems seem more like driver analysis problems, so I expect they'll be corrected soon. I know these aren't hardware limitations, because the camera can see the stupid pen, the driver just has to recognize it as a tool and disregard the hand holding it, which is really doesn't want to do - It's obsessed with hands. I should call it the Lyra driver from now on.

A more fundamental and concerning issue is the ease in which I can assume a position that blocks the camera's view of some or most of my fingers. Pretty much anything that involves my fingers being vertically aligned breaks the driver, along with everything from a roughly 90 degree to 135 degree angle, pointed away from the device. This appears to be an inherent issue with the device itself, and its the same problem the kinect would have, because the camera's view of the fingers gets blocked. How much more effective would a leap motion device with two cameras, one on either side of the monitor, be? Or just a wider camera angle (since it's using dual emitters anyway to get depth information). As it is right now, it's cute and futuristic looking, but any minority-report-esque gestures completely break it.

A much more unexpected issue is the fact that the device makes no attempt to deal with fingers that are held together, despite the fact that the shape of two touching fingers is fairly easy to figure out. If you've been tracking one finger and suddenly it meets up with another one and you end up with one really wide "finger", it should be trivial to send this information as a "double finger" pointing, because this is an incredibly useful gesture (see below for details). It's not like the finger is going to change into a hippopotamus all of a sudden.

3D Gestures
Most of the other problems are software oriented, not hardware or driver related. The simple fact is that no one has any idea how to properly utilize the device. Most apps seem to assume there's only going to be one finger pointed at the screen, and will get confused if you have any other fingers hanging off even if they're not pointed at the screen. The Leap Motion driver gives you a rough estimate of what it thinks the hand orientation is, and using this information its fairly trivial to figure out which finger someone is pointing with, even if their other fingers are only slightly below that finger. The camera is on a flat surface at a 90 degree angle from the screen, which means the finger you want is almost always going to be the finger that is the "highest" in relation to the hand orientation.

The rest of the apps either don't do much processing on the raw data, or do an incredibly bad job of it. The touch screen recreation had this horrible tendency to start sliding off, and the cursor would sometimes jump around. I knew it shouldn't be doing that because I've been watching the diagnostic information and it's just getting confused by ghost fingers popping in and out. Guess what? A finger can't teleport. If you've been tracking one finger, chances are you should keep tracking it no matter what else happens.

In addition, no one's really come up with effective 3D gestures. All the apps try to use the 3D plane by turning it into a virtual touchscreen and it doesn't work very well. Instead, we should be using gestures that are independent of a 2D plane. The apps need to be paying attention to the angle the finger is pointing in instead of trying to rely on moving your entire hand around. It seems like everyone is using the position information instead of the angle information, which the driver provides. If I'm pointing up and to the right, my cursor should be in the corner of the screen no matter where my hand is.

Furthermore, no one seems to be trying very hard to deal with noise. When the driver starts losing precision, you can tell because the angle information or position information will start to jitter. The more jittering, the less accurate the reading is. A simple way to quantify this is by calculating the variance of the recent data. The higher the variance, the less accurate your reading is. You should then scale how heavily you average out the points based on how much variance there is in the data. This allows you to avoid destroying precision while preventing the cursor from exploding when you lose accuracy. There's a lot of algorithms dedicated to solving this exact problem, so it's kind of ridiculous that no one is using them. In a more specific scenario, humans do precise manipulations with their fingers, not their hands. Small pertubations in the input data that occur in the hands should be removed from the finger positions, because it's just the hand trembling, not the actual finger.

Instead of trying to recreate "pushing a button" in 3D, we should use a gesture interface that lets you move the cursor around with your index finger, and then when you bring up your middle finger against your index finger (so you are now pointing at the screen with two fingers), this counts as a "click" or a mouse-down. You can then drag things around with two fingers, or separate them to generate a mouse-up event. To right-click, bring your two fingers together again, and then rotate your hand clockwise. This could be combined with a more traditional "pushing a button" gesture for easier clicks, but provides a much more robust way of moving things around that isn't awkward or difficult to use.

Since the driver currently doesn't let you track two fingers held together, this same behavior can be emulated by simply keeping track of two fingers and detecting when both of them accelerate towards each other until one of them vanishes. On this same note, because fingers can drop out of tracking, programs can't rely on the driver to be perfect. If you lose track of a finger, it's not that hard to guess where it might be based on the orientation of the hand, which is necessary if we're going to have good gesture recognition. The recognizer needs to be able to interpolate likely positions of lost fingers if it's going to make an effective guess about what gesture was intended.

Leap Motion is really cool. Leap Motion is definitely the future. Unfortunately, we haven't gotten to the future yet. We need a better software framework to build gesture interfaces on top of, and we need a new standard set of gestures for 3D that aren't simply 2D ripoffs. Incidentally, I'd love to try building an open-source library that addresses a lot of the input sanitation problems I outlined in this article, but I'm a bit busy with the whole "finding a job so I don't starve to death" thing. Hopefully, someone else will take up the cause, but until they do, don't expect to be very productive with the Leap Motion.

July 11, 2013

Aurora Theory Released!

Aurora Theory has been released! Buy it on bandcamp for $9, or $10 on iTunes, Amazon, and Google Play. The album is also available on Spotify, last.fm, other online radios, and can be previewed on YouTube.

Aurora Theory has been 4 years in the making, a compilation of all the songs I managed to make in the middle of attending university. The earlier songs have been extensively improved, and all songs have been remastered for the album's release. This album represents nothing less than the highest quality work I can possibly manage at this point in my career. I've acquired a fair number of fans over the years, and I want to thank you for supporting my musical endeavors so far.

Track List:
1. Soar (Original Mix) [5:49]
2. Aurora Theory (Redux) [4:10]
3. Cosminox [5:41]
4. Tendril [5:32]
5. Birefringence [3:57]
6. Critical Damage (Extended Mix) [3:45]
7. Starstruck [4:22]
8. Dream Among The Stars [4:06]
9. At The Nationals [4:02]
10. The Cloud River [5:38]
11. The Piano And The Cello [3:53]
12. Snowflower [5:53]
13. Spiral Nebula [5:44]
14. Next Year [5:31]

June 13, 2013

What I Learned In College

"In times of change, learners inherit the earth, while the learned find themselves beautifully equipped to deal with a world that no longer exists." ― Eric Hoffer
Yesterday, the University of Washington finally mailed me my diploma. A Bachelor of Science in Applied Computational Math and Science: Discrete Math and Algorithms. I learned a lot of things in college. I learned how to take tests and how to pinpoint exactly what useless crap a particular final needed me to memorize. I learned that math is an incredibly beautiful thing that has been butchered so badly I hated it all the way until my second year of college. I learned that creativity is useless and all problems have one specific right answer you can find in the back of a textbook somewhere, because that's all I was ever graded on. I learned that getting into the CSE major is more about fighting an enormous, broken bureaucratic mess than actually being good at computer science. But most of all, I learned that our educational system is so obsessed with itself it can't even recognize it's own shortcomings.

The first accelerated program I was accepted into was the Gifted program in middle school. I went from getting As in everything to failing every single one of my core classes. Determined to prove myself, I managed to recover my grades to Bs and Cs by the end of 7th grade, and by the end of 8th grade I was back up to As and Bs. I didn't do this by getting smarter, I did it by getting better at following directions. I got better at taking tests. I became adept at figuring out precisely what the teacher wanted me to do, and then doing only that, so I could maximize both my free time and my grades. By the time I reached high school, I would always meticulously go over the project requirements, systematically satisfying each bullet point in order to maximize my score. During tests, I not only skipped over difficult questions, I would actively seek out hints in the later questions to help me narrow down possible answers. My ability to squeeze out high grades had more to do with my aptitude at filling in the right bubbles on a piece of paper then actually understanding the material.

I fantasized about attending college, where I would be judged on my intellectual prowess, and not on my test taking skills. I longed for the pursuit of knowledge in it's purest form, only for this dream to be completely and utterly crushed. Instead of a place free from the endless battery of tests I had been subjected to during high school, I quickly realized that college was nothing but tests. I once had a math course where 95% of my grade was split between a first midterm, a second midterm, and a final. By the end of my second year of college, I simply stopped attending lectures. I could teach myself the material out of the textbook, and went to class only to take a test or turn in homework. I earned my degree by becoming incredibly adept at memorizing precisely which useless, specific facts were needed to properly answer questions. I was never asked nor told how to apply these to real world scenarios.

Thankfully, in one of the last classes I actually attended lecture in, the TA teaching the class said something that sparked a epiphany in me: "Math is simply repeated abstraction and generalization." Suddenly, I was able to connect math and programming, and began to realize that I had loved math all my life. What I hated about math was the trivial nonsense they taught in middle school. I signed up for the most advanced math classes I could get away with, even when I could barely pass them. I began to realize that the most important thing these classes taught me was what I didn't know. Once I knew what I didn't know, I could teach it to myself, but only after I found the holes in my knowledge. You can't fill a hole if you don't know where it is. I didn't know what combinatorics was until it was mentioned to me by that TA; Chrome still doesn't think combinatorics is even a word.

Everyone finds the beauty of math in their own way, but we teach it like an automated assembly line of cars. Math is taught as some kind of rigid tool, when it is really a language for expressing logic, one with multiple dialects, each with their own personality. We invented music to express emotions that cannot be described; we invented math to express logical abstractions that defy explanation. Every tool in math is like another instrument in a grand orchestra, each note echoing off the others, reflecting a whole that is greater than the sum of its parts. Some composers prefer the string section, others prefer the woodwinds. There is no single right answer, only different ones. Instead of giving our children a brush and telling them to use their imagination, we give them a coloring book and grade them on how well they stay inside the lines.

I mean, we all know creativity is overrated. It must be, since we systematically destroy it even when we try to encourage it. It doesn't matter how many programs we fund for encouraging things like art and music when the kids are still ultimately judged on how well they follow instructions and fill in little scantron bubbles. Kids are not stupid. I cannot believe how many adults still think they can get away with telling kids one thing and then doing another. They know what you're up to. They know the only thing the school system cares about is their grades, and that their grades are based entirely on how well they follow directions. They know that answering a question "almost right" doesn't matter. They know all problems have one answer in the back of the teacher's textbook, and their job is to figure out what it is. The vast majority of them have absolutely no idea how to approach a problem that has no correct answer. They don't know how to judge the correctness of a solution, because in school, everything is either right or wrong. All they know how to do is guess how likely it is that their solution is the solution the teacher wants, not how well the solution would actually work.

This is, of course, completely contradictory to everything in life. Life does not have answers in the back of the book. Life does not have a single correct answer to any problem. There is no right way to do anything, there are simply pros and cons. The fact that many people continue to delude themselves into thinking otherwise is a sad symptom of this issue. Our obsession with tests has trained a generation of robots, not engineers. They're more skilled at working their way through a bureaucracy than designing rockets. Then again, considering that colleges have now turned into enormous, obstructive bureaucracies, perhaps this isn't entirely a bad thing.

After all, with only 160 (now 200) spots open in its CSE major program each year when it has over 27000 undergraduate students enrolled[1], the University of Washington gets mighty picky about who they let in. After getting a 3.7 and 3.4 in my first two calculus classes, I slipped and got a 2.8 in my third math class, so despite the fact that I got a perfect 5 on the AP Computer Science AB exam and was qualified to skip both introductory programming courses, they rejected my application and demanded I take Matrix Algebra before letting me in. So I got a 3.9 in Matrix Algebra (a grade that was exceptionally good, according to one professor), and then... they still didn't let me in. They complained that my entrance essay sounded "too cocky" and had me take the second introductory programming course even though I already had credit for it. When I failed to get an exceptionally good grade in that class for all the wrong reasons (like being graded down for having both too few comments and too many comments in my code), I simply could not bring myself to compete in a hyper-competitive environment where the only thing I was judged on was how many irrelevant details I could regurgitate. So, I majored in Applied Mathematics and simply took all the condensed, non-major CSE courses instead.

This obsession with tests extends into the evaluation of the educational system itself. One of the reasons nothing is getting better is because we use the very thing that is wrong with the educational system to judge it. We fill out ridiculous polls made out of those same interminable bubbles that are destroying the curriculum. We introduce more standardized testing. The entire system is completely obsessed with tests, and yet the only place that tests actually exist is... inside the system itself. Education has become so enraptured with this imaginary world it has constructed, it's completely forgotten about the reality it's supposed to be teaching kids about.

Kids know this imaginary world has nothing to do with reality. We lament about how to teach kids math when they refuse to understand it, without realizing that they are simply applying the same method of learning they use in everything else - memorize useless facts, then regurgitate them on a test. The reason our math curriculum is failing so badly is because in math, you can't simply memorize things, you need to understand them. Consequently, Math acts as a canary in the coal mine for our entire educational system. Kids make no effort to understand anything, because they aren't graded on how well they understand concepts, they are graded on how well they memorize random, useless details and follow directions.

We live in a world being overrun by automation. Any task that can be reduced to simply following a set of instructions over and over is being done by robots and software. This constant attrition of jobs involving menial work and physical labor will continue at a steady pace for the foreseeable future. We are teaching our kids skills that are being made irrelevant in a modern economy. We are preparing our children for a world that no longer exists. At the same time, while I could write a series of blog posts outlining an effective educational system, it will never be implemented in public schools. The establishment is too deeply entrenched. Foolish startups repeatedly and continually attempt to "disrupt" the educational system without realizing just how laughably outmatched they are. This is not something you can fix with a cute website. People complain about global warming, space travel, all sorts of adorable little problems, but miss the elephant in the room.

The greatest challenge our species has ever faced is the educational system itself.

May 30, 2013

How To Complain About Men And Be Sexist At The Same Time

What if I told you about an article that complained about how social media and instant gratification has eroded away at our social fabric? How we don't take the time to pause and reflect on how we live our lives? How we fail to really work at making the world a better place, and instead waste time building websites to share cat photos on? I'd think that it raised several important issues about modern society.

What if I then told you that the entire article only applied this to men? What if it was titled, "Why Men Aren't Really Men Anymore"? Suddenly, things just got a lot more sexist. In fact, that entire article is built almost entirely out of gender stereotypes. It's that subtle, classy kind of sexism; bigotry that hides behind delicate prose, hiding it's true nature. If the article were rewritten so that it described these issues in gender-nuetral terms, I'd be liable to agree with it. Trolling, aggression, lack of human interaction, billions of dollars being spent on worthless startups that solve first world problems - these are all real issues. Yet, to imply that men are the ones with these problems, to imply that any class of problems belong to only one gender, is sexist.

The article is wonderfully subtle in its sexism. Just look at how it claims "real" men should treat women:

Real men are not selfish. Real men are just as concerned for the feelings, needs and minds of women as they are for their own — not just women’s bodies and their sexual usefulness. Real men have a well-defined code of ethics and respect that they follow.

Isn't that sweet? Except, oh wait, we have this disturbing sentence in the middle of the article:

Men have become lazy pussies. I don’t even want to use the word pussy because it brings to mind women, who nowadays have much more character than men.

Not to be outdone, the article's last paragraph contains this gem:

Some great women are settling for these fools and then finding that they themselves have no choice but to wear the pants in the family because their “man” is PMSing.

This is horribly sexist. These three sentences enforce multiple gender stereotypes and tell us a number of things:
  1. Women want manly men. If they think they don't want a manly man, they just haven't found one manly enough yet.
  2. Men are always the ones who should be wearing the pants in the family, because men always have to be the manly ones.
  3. Women shouldn't have more character than men.
  4. Women are allowed to be PMSing because they're women, and everyone knows women get emotional, but a man should never be emotional, because he's a man.

See, the reasoning behind all these is just "because men are men and women are women." That isn't a reason, it's sexism. It's bigotry. It's enforcing stereotypes and trying to tell people how they should live their lives based on a set of gender roles that society arbitrarily decided on. It simply assumes it knows what women want, and goes so far to imply that the only reason a women wouldn't want a "real" man is because they haven't seen one yet. This is exactly like those annoying little assholes who tell you "Oh you just haven't heard good dubstep! You'll like it then!" Inevitably, after you still don't like it, they just tell you that something is clearly wrong with you and you have no taste.

At no point do they entertain the notion that, maybe, just maybe, you actually don't like dubstep.

Our society suffers from the same tunnel vision. We assume that when a women is working overtime and the man is doing laundry that it's the man's fault for not being manly enough and the women has been forced to become the head of the household. If she had just married a man manly enough, she wouldn't have had to do that!

It never crosses their minds that maybe, just maybe, the women actually likes it this way. Maybe some men just don't want to be manly. Maybe some women like men who aren't manly. Maybe you can't fit every single human being into nice neat little gender boxes.

It is not a man's job to be manly simply because they are men. It is not a women's job to be PMSing or making you a sandwich. It is not society's place to tell anyone how they should live their lives. You do not know what they want and you should never pretend you do. We can make certain observations about genders, like men tend to be more aggressive, and women tend to be more emotional, but we should never assume that men should be more aggressive, or women should be more emotional. That is for the individual to decide, not society.

A human being is something precious, something complicated, something that can't be easily categorized. Stop trying to stuff them into square boxes.

May 25, 2013

Course Notes

It's standard procedure at the University of Washington to allow a single sheet of handwritten notes during a Mathematics exam. I started collecting these sheets after I realized how useful it was to have a reference that basically summarized all the useful parts of the course on a single sheet of paper. Now that I've graduated, it's easy for me to quickly forget all the things I'm not using. The problem is that, when I need to say, develop an algorithm for simulating turbulent airflow, I need to go back and re-learn vector calculus, differential equations and nonlinear dynamics. So I've decided to digitize all my notes and put them in one place where I can reference them. I've uploaded it here in case they come in handy to anyone else.

The earlier courses listed here had to be reconstructed from my class notes because I'd thrown my final notesheet away or otherwise lost it. The classes are not listed in the order I took them, but rather organized into related groups. This post may be updated later with expanded explanations for some concepts, but these are highly condensed notes for reference, and a lot of it won't make sense to someone who hasn't taken a related course.

Math 124 - Calculus I
lost

Math 125 - Calculus II
lost

Math 126 - Calculus III
lost

Math 324 - Multivariable Calculus I
\[ r^2 = x^2 + y^2 \]
\[ x= r\cos\theta \]
\[ y=r\sin\theta \]

\[ \iint\limits_R f(x,y)\,dA = \int_\alpha^\beta\int_a^b f(r\cos\theta,r\sin\theta)r\,dr\,d\theta=\int_\alpha^\beta\int_{h_1(\theta}^{h_2(\theta)} f(r\cos\theta,r\sin\theta)r\,dr\,d\theta \]

\[ m=\iint\limits_D p(x,y)\,dA \begin{cases} M_x=\iint\limits_D y p(x,y)\,dA & \bar{x}=\frac{M_y}{m}=\frac{1}{m}\iint x p(x,y)\,dA \\ M_y=\iint\limits_D x p(x,y)\,dA & \bar{y}=\frac{M_x}{m}=\frac{1}{m}\iint y p(x,y)\,dA \end{cases} \]

\[ Q = \iint\limits_D \sigma(x,y)\,dA \]
\[ I_x = \iint\limits_D y^2 p(x,y)\,dA \]
\[ I_y = \iint\limits_D x^2 p(x,y)\,dA \]
\[ I_0 = \iint\limits_D (x^2 + y^2) p(x,y)\,dA \]

\[ \iiint f(x,y,z) dV = \lim_{l,m,n\to\infty}\sum_{i=1}^l\sum_{j=1}^m\sum_{k=1}^n f(x_i,y_j,z_k) \delta V \]
\[ \iiint\limits_B f(x,y,z)\,dV=\int_r^s\int_d^c\int_a^b f(x,y,z)\,dx\,dy\,dz = \int_a^b\int_r^s\int_d^c f(x,y,z)\,dy\,dz\,dx \]

$$E$$ = general bounded region
Type 1: $$E$$ is between graphs of two continuous functions of $$x$$ and $$y$$.
\[ E=\{(x,y,z)|(x,y)\in D, u_1(x,y) \le z \le u_2(x,y)\} \]

$$D$$ is the projection of E on to the xy-plane, where
\[ \iiint\limits_E f(x,y,z)\,dV = \iint\limits_D\left[\int_{u_1(x,y)}^{u_2(x,y)} f(x,y,z)\,dz \right]\,dA \]

$$D$$ is a type 1 planar region:
\[ \iiint\limits_E f(x,y,z)\,dV = \int_a^b \int_{g_1(x)}^{g_2(x)} \int_{u_1(x,y)}^{u_2(x,y)} f(x,y,z)\,dz\,dy\,dx \]

$$D$$ is a type 2 planar region:
\[ \iiint\limits_E f(x,y,z)\,dV = \int_d^c \int_{h_1(y)}^{h_2(y)} \int_{u_1(x,y)}^{u_2(x,y)} f(x,y,z)\,dz\,dx\,dy \]


Type 2: $$E$$ is between $$y$$ and $$z$$, $$D$$ is projected on to $$yz$$-plane
\[ E=\{(x,y,z)|(y,z)\in D, u_1(y,z) \le x \le u_2(y,z)\} \]
\[ \iiint\limits_E f(x,y,z)\,dV = \iint\limits_D\left[\int_{u_1(y,z)}^{u_2(y,z)} f(x,y,z)\,dx \right]\,dA \]

Type 3: $$E$$ is between $$x$$ and $$z$$, $$D$$ is projected on to $$xz$$-plane
\[ E=\{(x,y,z)|(x,z)\in D, u_1(x,z) \le y \le u_2(x,z)\} \]
\[ \iiint\limits_E f(x,y,z)\,dV = \iint\limits_D\left[\int_{u_1(x,z)}^{u_2(x,z)} f(x,y,z)\,dy \right]\,dA \]

Mass
\[ m = \iiint\limits_E p(x,y,z)\,dV \]
\[ \bar{x} = \frac{1}{m}\iiint\limits_E x p(x,y,z)\,dV \]
\[ \bar{y} = \frac{1}{m}\iiint\limits_E y p(x,y,z)\,dV \]
\[ \bar{z} = \frac{1}{m}\iiint\limits_E z p(x,y,z)\,dV \]
Center of mass: $$(\bar{x},\bar{y},\bar{z})$$
\[ Q = \iiint\limits_E \sigma(x,y,z)\,dV \]
\[ I_x = \iiint\limits_E (y^2 + z^2) p(x,y,z)\,dV \]
\[ I_y = \iiint\limits_E (x^2 + z^2) p(x,y,z)\,dV \]
\[ I_z = \iiint\limits_E (x^2 + y^2) p(x,y,z)\,dV \]

Spherical Coordinates:
\[ z=p\cos\phi \]
\[ r=p\sin\phi \]
\[ dV=p^2\sin\phi \]
\[ x=p\sin\phi\cos\theta \]
\[ y=p\sin\phi\sin\theta \]
\[ p^2 = x^2 + y^2 + z^2 \]
\[ \iiint\limits_E f(x,y,z)\,dV = \int_c^d\int_\alpha^\beta\int_a^b f(p\sin\phi\cos\theta,p\sin\phi\sin\theta,p\cos\phi) p^2\sin\phi\,dp\,d\theta\,d\phi \]

Jacobian of a transformation $$T$$ given by $$x=g(u,v)$$ and $$y=h(u,v)$$ is:
\[ \frac{\partial (x,y)}{\partial (u,v)} = \begin{vmatrix} \frac{\partial x}{\partial u} & \frac{\partial x}{\partial v} \\ \frac{\partial y}{\partial u} & \frac{\partial y}{\partial v} \end{vmatrix} = \frac{\partial x}{\partial u} \frac{\partial y}{\partial v} - \frac{\partial x}{\partial v} \frac{\partial y}{\partial u} \]

Given a transformation T whose Jacobian is nonzero, and is one to one:
\[ \iint\limits_R f(x,y)\,dA = \iint\limits_S f\left(x(u,v),y(u,v)\right)\left|\frac{\partial (x,y)}{\partial (u,v)}\right|\,du\,dv \]

Polar coordinates are just a special case:
\[ x = g(r,\theta)=r\cos\theta \]
\[ y = h(r,\theta)=r\sin\theta \]

\[ \frac{\partial (x,y)}{\partial (u,v)} = \begin{vmatrix} \frac{\partial x}{\partial r} & \frac{\partial x}{\partial \theta} \\ \frac{\partial y}{\partial r} & \frac{\partial y}{\partial \theta} \end{vmatrix} = \begin{vmatrix} \cos\theta & -r\sin\theta \\ \sin\theta & r\cos\theta \end{vmatrix} = r\cos^2\theta + r\sin^2\theta=r(\cos^2\theta + \sin^2\theta) = r \]

\[ \iint\limits_R f(x,y)\,dx\,dy = \iint\limits_S f(r\cos\theta, r\sin\theta)\left|\frac{\partial (x,y)}{\partial (u,v)}\right|\,dr\,d\theta=\int_\alpha^\beta\int_a^b f(r\cos\theta,r\sin\theta)|r|\,dr\,d\theta\]

For 3 variables this expands as you would expect: $$x=g(u,v,w)$$ $$y=h(u,v,w)$$ $$z=k(u,v,w)$$
\[ \frac{\partial (x,y,z)}{\partial (u,v,w)}=\begin{vmatrix} \frac{\partial x}{\partial u} & \frac{\partial x}{\partial v} & \frac{\partial x}{\partial w} \\ \frac{\partial y}{\partial u} & \frac{\partial y}{\partial v} & \frac{\partial y}{\partial w} \\ \frac{\partial z}{\partial u} & \frac{\partial z}{\partial v} & \frac{\partial z}{\partial w} \end{vmatrix} \]

\[ \iiint\limits_R f(x,y,z)\,dV = \iiint\limits_S f(g(u,v,w),h(u,v,w),k(u,v,w)) \left|\frac{\partial (x,y,z)}{\partial (u,v,w)} \right| \,du\,dv\,dw\]

Line Integrals
Parameterize: $$r(t)=\langle x(t),y(t),z(t) \rangle$$ where $$r'(t)=\langle x'(t),y'(t),z'(t) \rangle$$ and $$|r'(t)|=\sqrt{x'(t)^2 + y'(t)^2 + z'(t)^2} $$
\[ \int_C f(x,y,z)\,ds = \int_a^b f(r(t))\cdot |r'(t)|\,dt = \int_a^b f(x(t),y(t),z(t))\cdot\sqrt{x'(t)^2 + y'(t)^2 + z'(t)^2}\,dt\;\;\;a<t<b \]

For a vector function $$\mathbf{F}$$:
\[ \int_C \mathbf{F}\cdot dr = \int_a^b \mathbf{F}(r(t))\cdot r'(t)\,dt \]

Surface Integrals
\[ \]

Parameterize: $$r(u,v) = \langle x(u,v),y(u,v),z(u,v) \rangle$$
\[ \begin{matrix} r_u=\frac{\partial x}{\partial u}\vec{\imath} + \frac{\partial y}{\partial u}\vec{\jmath} + \frac{\partial z}{\partial u}\vec{k} \\ r_v=\frac{\partial x}{\partial v}\vec{\imath} + \frac{\partial y}{\partial v}\vec{\jmath} + \frac{\partial z}{\partial v}\vec{k} \end{matrix}\]
\[ r_u \times r_v = \begin{vmatrix} \vec{\imath} & \vec{\jmath} & \vec{k} \\ \frac{\partial x}{\partial u} & \frac{\partial y}{\partial u} & \frac{\partial z}{\partial u} \\ \frac{\partial x}{\partial v} & \frac{\partial y}{\partial v} & \frac{\partial z}{\partial v} \end{vmatrix} \]

\[ \iint\limits_S f(x,y,z) dS = \iint\limits_D f(r(t))|r_u \times r_v|\,dA \]

For a vector function $$\mathbf{F}$$:
\[ \iint\limits_S \mathbf{F}\cdot dr = \iint\limits_D \mathbf{F}(r(u,v))\cdot (r_u \times r_v)\,dA) \]

Any surface $$S$$ with $$z=g(x,y)$$ is equivalent to $$x=x$$, $$y=y$$, and $$z=g(x,y)$$, so
$$xy$$ plane:
\[ \iint\limits_S f(x,y,z)\,dS = \iint\limits_D f(x,y,g(x,y))\sqrt{\left(\frac{\partial z}{\partial x}\right)^2+\left(\frac{\partial z}{\partial y}\right)^2+1}\,dA \]

$$yz$$ plane:
\[ \iint\limits_S f(x,y,z)\,dS = \iint\limits_D f(x,h(x,z),z)\sqrt{\left(\frac{\partial y}{\partial x}\right)^2+\left(\frac{\partial y}{\partial z}\right)^2+1}\,dA \]

$$xz$$ plane:
\[ \iint\limits_S f(x,y,z)\,dS = \iint\limits_D f(g(y,z),y,z)\sqrt{\left(\frac{\partial x}{\partial y}\right)^2+\left(\frac{\partial x}{\partial z}\right)^2+1}\,dA \]

Flux:
\[ \iint\limits_S\mathbf{F}\cdot dS = \iint\limits_D\mathbf{F}\cdot (r_u \times r_v)\,dA \]

The gradient of $$f$$ is the vector function $$\nabla f$$ defined by:
\[ \nabla f(x,y)=\langle f_x(x,y),f_y(x,y)\rangle = \frac{\partial f}{\partial x}\vec{\imath} + \frac{\partial f}{\partial y}\vec{\jmath} \]

Directional Derivative:
\[D_u\,f(x,y) = f_x(x,y)a + f_y(x,y)b = \nabla f(x,y)\cdot u \text{ where } u = \langle a,b \rangle \]
\[ \int_C\,ds=\int_a^b |r'(t)|=L \]
\[ \]

If $$\nabla f$$ is conservative, then:
\[ \int_{c_1} \nabla f\,dr=\int_{c_2} \nabla f\,dr \]

This means that the line integral between two points will always be the same, no matter what curve is used to go between the two points - the integrals are path-independent and consequently only depend on the starting and ending positions in the conservative vector field.
A vector function is conservative if it can be expressed as the gradient of some potential function $$\psi$$: $$\nabla \psi = \mathbf{F}$$
\[ curl\,\mathbf{F} =\nabla\times\mathbf{F}\]
\[ div\,\mathbf{F} =\nabla\cdot\mathbf{F}\]


Math 326 - Multivariable Calculus II
$$f(x,y)$$ is continuous at a point $$(x_0,y_0)$$ if
\[ \lim\limits_{(x,y)\to(0,0)} f(x,y) = f(x_0,y_0) \]

$$f+g$$ is continuous if $$f$$ and $$g$$ are continuous, as is $$\frac{f}{g}$$ if $$g \neq 0$$
A composite function of a continuous function is continuous
\[ \frac{\partial f}{\partial x} = f_x(x,y) \]
\[ \frac{\partial f}{\partial x}\bigg|_{(x_0,y_0)}=\left(\frac{\partial f}{\partial x}\right)_{(x_0,y_0)}=f_x(x_0,y_0) \]

To find $$\frac{\partial z}{\partial x} F(x,y,z)$$, differentiate $$x$$ as normal, hold y constant, and differentiate $$z$$ as a function (such that $$z^2 = 2z \frac{\partial z}{\partial x}$$ and $$2z = 2 \frac{\partial z}{\partial x}$$)
Ex:
\[ F(x,y,z) = \frac{x^2}{16} + \frac{y^2}{12} + \frac{z^2}{9} = 1 \]
\[ \frac{\partial z}{\partial x} F = \frac{2x}{16} + \frac{2z}{}\frac{\partial z}{\partial x} = 0 \]

The tangent plane of $$S$$ at $$(a,b,c): z-c = f_x(a,b)(x-a) + f_y(a,b)(y-b)$$ where $$z=f(x,y)$$, or $$z =f(a,b) + f_x(a,b)(x-a) + f_y(a,b)(y-b)$$
Note that
\[ f_x(a,b)=\frac{\partial z}{\partial x}\bigg|_{(a,b)} \]
which enables you to find tangent planes implicitly.
Set $$z=f(x,y)$$. $$f_x=f_y=0$$ at a relative extreme $$(a,b)$$.
Distance from origin:
\[ D^2 = z^2 + y^2 + x^2 = f(a,b)^2 + y^2 + x^2 \]

Minimize $$D$$ to get point closest to the origin.
The differential of $$f$$ at $$(x,y)$$:
\[ df(x,y;dx,dy)=f_x(x,y)\,dx + f_y(x,y)\,dy \]
\[ dz=\frac{\partial f}{\partial x}\,dx + \frac{\partial f}{\partial y}\,dy \]

$$f$$ is called differentiable at $$(x,y)$$ if it $$s$$ defined for all points near $$(x,y)$$ and if there exists numbers $$A$$,$$B$$ such that
\[ \lim_{(n,k)\to(0,0)}\frac{|f(x+h,y+k) - f(x,y) - Ah - Bk|}{\sqrt{h^2 + k^2}}=0 \]

If $$f$$ is differentiable at $$(x,y)$$ it is continuous there.
\[ A = f_x(x,y) \]
and
\[ B=f_y(x,y) \]

If $$F_x(x,y)$$ and $$F_y(x,y)$$ are continuous at a point $$(x_0,y_0)$$ defined in $$F$$, then $$F$$ is differentiable there.
Ex: The differential of $$f(x,y)=3x^2y+2xy^2+1$$ at $$(1,2)$$ is $$df(1,2;h,k)=20h+11k$$
\[ d(u+v)=du+dv \]
\[ d(uv)=u\,dv + v\,du \]
\[ d\left(\frac{u}{v}\right)=\frac{v\,du -u\,dv}{v^2} \]

Taylor Series:
\[ f^{(n)}(t)=\left[\left(h\frac{}{} + k\frac{}{})^n F(x,y) \right) \right]_{x=a+th,y=b+tk} \]
Note:
\[ f''(t)=h^2 F_{xx} + 2hk F_{xy} + k^2 F_{yy} \]

\[ \begin{matrix} x=f(u,v) \\ y=g(u,v) \end{matrix} \]
\[ J=\frac{\partial(f,g)}{\partial(u,v)} \]
\[ \begin{matrix} u=F(x,y) \\ v=G(x,y) \end{matrix} \]
\[ j = J^{-1} = \frac{1}{\frac{\partial(f,g)}{\partial(u,v)}} \]

\[ \begin{matrix} x = u-uv \\ y=uv \end{matrix} \]
\[ \iint\limits_R\frac{dx\,dy}{x+y} \]
R bounded by
\[ \begin{matrix} x+y=1 & x+y=4 \\ y=0 & x=0 \end{matrix}\]
\[ \int_0^1\int_0^x \frac{du\,dv}{u-uv+ux}\left|\frac{\partial(x,y)}{\partial(u,v)}\right| \]

\[ \frac{\partial(F,G)}{\partial(u,v)}=\begin{vmatrix} \frac{\partial F}{\partial u} & \frac{\partial F}{\partial v} \\ \frac{\partial G}{\partial u} & \frac{\partial G}{\partial v} \end{vmatrix} \]
\[ \nabla f = \langle f_x, f_y, f_z \rangle \]
\[ G_x(s_0,t_0) =F_x(a,b)f_x(s_0,t_0) + F_y(a,b)g_x(s_0,t_0) \]
\[ U\times V = U_xV_y - U_yV_x \text{ or } A\times B = \left\langle \begin{vmatrix} a_y & a_z \\ b_y & b_z \end{vmatrix}, -\begin{vmatrix} a_x & a_z \\ b_x & b_z \end{vmatrix}, \begin{vmatrix} a_x & a_y \\ b_x & b_y \end{vmatrix} \right\rangle \]

Given $$G(s,t)=F(f(s,t),g(s,t))$$, then:
\[ \begin{matrix} \frac{\partial G}{\partial s} = \frac{\partial F}{\partial x}\frac{\partial f}{\partial s} + \frac{\partial F}{\partial y}\frac{\partial g}{\partial s} \\ \frac{\partial G}{\partial t} = \frac{\partial F}{\partial x}\frac{\partial f}{\partial t} + \frac{\partial F}{\partial y}\frac{\partial g}{\partial t} \end{matrix} \]

Alternatively, $$ u=F(x,y,z)=F(f(t),g(t),h(t))$$ yields
\[ \frac{du}{dt}=\frac{\partial u}{\partial x}\frac{dx}{dt} + \frac{\partial u}{\partial y}\frac{dy}{dt} + \frac{\partial u}{\partial z}\frac{dz}{dt} \]

Examine limit along line $$y=mx$$:
\[ \lim_{x\to 0} f(x,mx) \]

If $$g_x$$ and $$g_y$$ are continuous, then $$g$$ is differentiable at that point (usually $$0,0$$).
Notice that if $$f_x(0,0)=0$$ and $$f_y(0,0)=0$$ then $$df(0,0;h,l)=0h+0k=0$$

The graph of $$y(x,y)$$ lies on a level surface $$F(x,y,z)=c$$ means $$f(x,y(x,z),z)=c$$. So then use the chain rule to figure out the result in terms of $$F$$ partials by considering $$F$$ a composite function $$F(x,y(x,z),z)$$.

Fundamental implicit function theorem: Let $$F(x,y,z)$$ be a function defined on an open set $$S$$ containing the point $$(x_0,y_0,z_0)$$. Suppose $$F$$ has continuous partial derivatives in $$S$$. Furthermore assume that: $$F(x_0,y_0,z_0)=0, F_z(x_0,y_0,z_0)\neq 0$$. Then $$z=f(x,y)$$ exists, is continuous, and has continuous first partial derivatives.
\[ f_x = -\frac{F_x}{F_z} \]
\[ f_y = -\frac{F_y}{F_z} \]

Alternatively, if
\[ \begin{vmatrix} F_x & F_y \\ G_x & G_y \end{vmatrix} \neq 0 \]
, then we can solve $$x$$ and $$y$$ as functions of $$z$$. Since the cross-product is made of these determinants, if the $$x$$ component is nonzero, you can solve $$y,z$$ as functions of $$x$$, and therefore graph it on the $$x-axis$$.

To solve level surface equations, let $$F(x,y,z)=c$$ and $$G(x,y,z)=d$$, then use the chain rule, differentiating by the remaining variable (e.g. $$\frac{dy}{dx}$$ and $$\frac{dz}{dx}$$ means do $$x$$)
\[ \begin{matrix} F_x + F_y y_x + F_z z_x = 0 \\ G_x + G_y y_x + G_z z_x = 0 \end{matrix} \]
if you solve for $$y_x$$,$$z_x$$, you get
\[ \left[ \begin{matrix} F_y & F_z \\ G_y & G_z \end{matrix} \right] \left[ \begin{matrix} y_x \\ z_x \end{matrix} \right] = \left[\begin{matrix}F_x \\ G_x \end{matrix} \right] \]

Mean value theorem:
\[ f(b) - f(a) = (b-a)f'(X) \]
\[ a < X < b \]

or:
\[ f(a+h)=f(a)+hf'(a + \theta h) \]
\[ 0 < \theta < 1 \]

xy-plane version:
\[ F(a+h,b+k)-F(a,b)=h F_x(a+\theta h,b+\theta k)+k F_y(a+\theta h, b+\theta k) \]
\[ 0 < \theta < 1 \]

Lagrange Multipliers: $$\nabla f = \lambda\nabla g$$ for some scale $$\lambda$$ if $$(x,y,z)$$ is a minimum:
\[ f_x=\lambda g_x \]
\[ f_y=\lambda g_y \]
\[ f_z=\lambda g_z \]
Set $$f=x^2 + y^2 + z^2$$ for distance and let $$g$$ be given.

Math 307 - Introduction to Differential Equations
lost

Math 308 - Matrix Algebra
lost

Math 309 - Linear Analysis
lost

AMath 353 - Partial Differential Equations

Fourier Series:
\[ f(x)=b_0 + \sum_{n=1}^{\infty} \left(a_n \sin\frac{n\pi x}{L} + b_n\cos\frac{n\pi x}{L} \right) \]
\[ b_0 = \frac{1}{2L}\int_{-L}^L f(y)\,dy \]
\[ a_m \frac{1}{L}\int_{-L}^L f(y) \sin\frac{m\pi y}{L}\,dy \]
\[ b_m = \frac{1}{L}\int_{-L}^L f(y)\cos\frac{m\pi y}{L}\,dy \]
\[ m \ge 1 \]

\[ u_t=\alpha^2 u_{xx} \]
\[ \alpha^2 = \frac{k}{pc} \]
\[ u(x,t)=F(x)G(t) \]

Dirichlet: $$u(0,t)=u(L,t)=0$$
Neumann:$$u_x(0,t)=u_x(L,t)=0$$
Robin:$$a_1 u(0,t)+b_1 u_x(0,t) = a_2 u(L,t) + b_2 u_x(L,t) = 0$$
Dirichlet:
\[ \lambda_n=\frac{n\pi}{L}\;\;\; n=1,2,... \]
\[ u(x,t)=\sum_{n=1}^{\infty} A_n \sin\left(\frac{n\pi x}{L} \right)\exp\left(-\frac{n^2\alpha^2\pi^2 t}{L^2}\right) \]
\[ A_n = \frac{2}{L} \int_0^L f(y) \sin\frac{n\pi y}{L}\,dy = 2 a_m\text{ for } 0\text{ to } L \]

Neumann:
\[ \lambda_n=\frac{n\pi}{L}\;\;\; n=1,2,... \]
\[ u(x,t)=B_0 + \sum_{n=1}^{\infty} B_n \cos\left(\frac{n\pi x}{L} \right)\exp\left(-\frac{n^2\alpha^2\pi^2 t}{L^2}\right) \]
\[ B_0 = \frac{1}{L} \int_0^L f(y)\,dy \]
\[ B_n = \frac{2}{L} \int_0^L f(y) \cos\frac{n\pi y}{L}\,dy = 2 b_m\text{ for } 0\text{ to } L \]

Dirichlet/Neumann:
\[ \lambda_n=\frac{\pi}{2L}(2n + 1)\;\;\; n=0,1,2,... \]
\[ u(x,t)=\sum_{n=0}^{\infty} A_n \sin\left(\lambda_n x\right) \exp\left(-\alpha^2 \lambda_n^2 t\right) \]
\[ A_n = \frac{2}{L} \int_0^L f(y) \sin\left(\lambda_n y\right)\,dy \]

Neumann/Dirichlet:
\[ \lambda_n=\frac{\pi}{2L}(2n + 1)\;\;\; n=0,1,2,... \]
\[ u(x,t)=\sum_{n=0}^{\infty} B_n \cos\left(\lambda_n x\right) \exp\left(-\alpha^2 \lambda_n^2 t\right) \]
\[ B_n = \frac{2}{L}\int_0^L f(y)\cos(\lambda_n y)\,dy \]

\[ v_2(x,y)=\sum_{n=1}^{\infty} C_n(t)[\sin/\cos](\lambda_n x) \]
Replace $$[\sin/\cos]$$ with whatever was used in $$u(x,t)$$
\[ C_n(t)=\int_0^t p_n(s) e^{\lambda_n^2\alpha^2 (s-t)}\,ds \]
\[ p_n(t)=\frac{2}{L}\int_0^L p(y,t)[\sin/\cos](\lambda_n y)\,dy \]
Replace $$[\sin/\cos]$$ with whatever was used in $$u(x,t)$$. Note that $$\lambda_n$$ for $$C_n$$ and $$p_n(t)$$ is the same as used for $$u_1(x,t)$$
Sturm-Liouville:
\[ p(x)\frac{d^2}{dx^2}+p'(x)\frac{d}{dx}+q(x) \]
\[ a_2(x)\frac{d^2}{dx^2} + a_1(x)\frac{d}{dx} + a_0(x) \rightarrow p(x)=e^{\int\frac{a_1(x)}{a_2(x)}\,dx}\]
\[ q(x)=p(x)\frac{a_0(x)}{a_2(x)} \]

Laplace's Equation:
\[ \nabla^2 u=0 \]
\[ u=F(x)G(y) \]
\[ \frac{F''(x)}{F(x)} = -\frac{G''(y)}{G(y)} = c \]
for rectangular regions
\[ F_?(x)=A =\sinh(\lambda x) + B \cosh(\lambda x) \]
use odd $$\lambda_n$$ if $$F$$ or $$G$$ equal a single $$\cos$$ term.
\[ G_?(y)=C =\sinh(\lambda y) + D \cosh(\lambda y) \]
\[ u(x,?)=G(?) \]
\[ u(?,y)=F(y) \]

Part 1: All $$u_?(x,?)=0$$
\[ \lambda_n=\frac{n\pi}{L y}\text{ or }\frac{(2n+1)\pi}{2L y} \]
\[ u_1(x,y)=\sum_{n=0}^{\infty}A_n F_1(x)G_1(y) \]
\[ A_n = \frac{2}{L_y F_1(?)}\int_0^{L_y} u(?,y)G_1(y)\,dy \]
\[ u(?,y)=h(y) \]
\[ ? = L_x\text{ or }0 \]

Part 2: All $$u_?(?,y)=0$$
\[ \lambda_n=\frac{n\pi}{L x}\text{ or }\frac{(2n+1)\pi}{2L x} \]
\[ u_2(x,y)=\sum_{n=1}^{\infty}B_n F_2(x)G_2(y) \]
\[ B_n = \frac{2}{L_x G_2(?)}\int_0^{L_x} u(x,?)F_2(x)\,dx \]
\[ u(x,?)=q(x) \]
\[ ? = L_y\text{ or }0 \]

\[ u(x,y)=u_1(x,y)+u_2(x,y) \]

Circular $$\nabla^2 u$$:
\[ u_{rr} + \frac{1}{r} u_r + \frac{1}{r^2}u_{\theta \theta} = 0 \]
\[ \frac{G''(\theta)}{G(\theta)}= - \frac{r^2 F''(r) + r F(r)}{F(r)} = c\]

\[ \left\langle f,g \right\rangle = \int_a^b f(x) g(x)\,dx \]
\[ \mathcal{L}_s=-p(x)\frac{d^2}{dx^2}-p'(x)\frac{d}{dx} + q(x) \]
\[ \mathcal{L}_s\phi(x)=\lambda r(x) \phi(x) \]
\[ \left\langle\mathcal{L}_s y_1,y_2 \right\rangle =\int_0^L \left(-[p y_1']'+q y_1\right)y_2\,dx \]

$$\mathcal{L}_s = f(x)$$, then $$\mathcal{L}_s^{\dagger} v(x) = 0$$, where if $$v=0$$, $$u(x)$$ is unique, otherwise $$v(x)$$ exists only when forcing is orthogonal to all trivial solutions.
if $$c=0$$,
\[ G(\theta)=B \]
\[ F(r)=C\ln r + D \]

if $$c=-\lambda^2 <0$$,
\[ G(\theta)=A\sin(\lambda\theta) + B\cos(\lambda\theta) \]
\[ F(r) = C\left(\frac{r}{R} \right)^n + D\left( \frac{r}{R} \right)^{-n}\]
\[ u(r,\theta)=B_0 + \sum_{n=1}^{\infty} F(r) G(\theta) = B_0 + \sum_{n=1}^{\infty}F(r)[A_n\sin(\lambda\theta) + B_n\cos(\lambda\theta)] \]
\[ A_n = \frac{1}{\pi}\int_0^{2\pi} f(\theta)\sin(n\theta)\,d\theta \]
\[ B_n = \frac{1}{\pi}\int_0^{2\pi} f(\theta)\cos(n\theta)\,d\theta \]
\[ B_0 = \frac{1}{2\pi}\int_0^{2\pi} f(\theta)\,d\theta \]

Wave Equation:
\[ u_{tt}=c^2 u_{xx} \]
\[ u = F(x)G(t) \]
\[ \frac{F''(x)}{F(x)}=\frac{G''(t)}{G(t)}=k \text{ where } u(t,0)=F(0)=u(t,L)=F(L)=0 \]
\[ F(x) = A\sin(\lambda x) + B\cos(\lambda x) \]
\[ u_t(x,0)=g(x)=\sum_{n=1}^{\infty} A_n\lambda_n c \sin(\lambda_n x) \]
\[ A_n = \frac{2}{\lambda_n c L}\int_0^L g(y)\sin(\lambda_n y)\,dy \]

\[ G(t) = C\sin(\lambda t) + D\cos(\lambda t) \]
\[ u(x,0)=f(x)=\sum_{n=1}^{\infty}B_n\sin(\lambda_n x) \]
\[ B_n = \frac{2}{L}\int_0^L f(y)\sin(\lambda_n y)\,dy \]

\[ u(x,t)=\sum_{n=1}^{\infty}F(x)G(t)=\sum_{n=1}^{\infty}F(x)\left[C\sin(\lambda t) + D\cos(\lambda t)\right] \]
\[ \lambda_n=\frac{n\pi}{L}\text{ or }\frac{(2n+1)\pi}{2L} \]

Inhomogeneous:
\[ u(0,t)=F(0)=p(t) \]
\[ u(L,t)=F(L)=q(t) \]
\[ u(x,t)=v(x,t) + \phi(x)p(t) + \psi(x)q(t) \]

Transform to forced:
\[ v(x,y) = \begin{cases} v_{tt}=c^2 v_{xx} - \phi(x)p''(x) - \psi(x)q''(t) = c^2 v_{xx} + R(x,t) & \phi(x)=1 - \frac{x}{L}\;\;\;\psi(x)=\frac{x}{L}\\ v(0,t)=v(L,t)=0 & t>0 \\ v(x,0)=f(x)-\phi(x)p(0) - \psi(x)q(0) & f(x)=u(x,0) \\ v_t(x,0)=g(x)-\phi(x)p'(0) - \psi(x)q'(0) & g(x)=u_t(x,0) \end{cases} \]

Then solve as a forced equation.
Forced:
\[ u_{tt}=c^2 u_{xx} + R(x,t) \]
\[ u(x,t)=u_1(x,t)+u_2(x,t) \]
$$u_1$$ found by $$R(x,t)=0$$ and solving.
\[ u_2(x,t)=\sum_{n=1}^{\infty} C_n(t)\sin\left(\frac{n\pi x}{L}\right) \]
where $$\sin\frac{n\pi x}{L}$$ are the eigenfunctions from solving $$R(x,t)=0$$
\[ R(x,t)=\sum_{n=1}^{\infty} R_n(t)\sin\left(\frac{n\pi x}{L}\right) \]
\[ R_n(t)=\frac{2}{L}\int_0^L R(y,t)\sin\left(\frac{n\pi x}{L}\right)\,dy \]
\[ C_n''(t) + k^2 C_n(t)=R_n(t) \]
\[ C_n(t)=\alpha\sin(k t) + \beta\cos(k t) + sin(k t)\int_0^t R_n(s)\cos(k s)\,ds - \cos(k t)\int_0^t R_n(s)\sin(k s)\,ds \]

where $$C_n(0)=0$$ and $$c_n'(0)=0$$
Fourier Transform:
\[ \mathcal{F}(f)=\hat{f}(k)=\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{\infty} f(\xi) e^{-i k \xi}\,d\xi \]
\[ \mathcal{F}^{-1}(f)=f(x)=\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{\infty} \hat{f}(k) e^{ikx}\,dk \]
\[ \mathcal{F}(f+g)=\widehat{f+g}=\hat{f} + \hat{g} \]
\[ \widehat{fg}\neq\hat{f}\hat{g} \]
\[ \widehat{f'}=ik\hat{f}\text{ or }\widehat{f^{(n)}}=(ik)^n\hat{f} \]

\[ \widehat{u_t} = \frac{\partial \hat{u}}{\partial t} = \hat{u}_t \]
\[ \widehat{u_{tt}}=\frac{\partial^2\hat{u}}{\partial t^2}=\hat{u}_{tt} \]
\[ \widehat{u_{xx}}=(ik)^2\hat{u}=-k^2\hat{u} \]

\[ u(x,t)=\mathcal{F}^{-1}(\hat{u})=\frac{1}{\sqrt{2\pi}} \int_{-\infty}^{\infty} \hat{f}(k) e^{\alpha^2 k^2 t} e^{ikx}\,dk \]
\[ u(x,t)=\mathcal{F}^{-1}\left(\hat{f}(k) e^{-\alpha^2 k^2 t}\right) \]

Semi-infinite:
\[ \frac{1}{\sqrt{2\pi}} \int_{-\infty}^{\infty} \hat{F}(k) e^{\alpha^2 k^2 t} e^{ikx}\,dk \]
where
\[ \hat{F}(k)=-i\sqrt{\frac{2}{\pi}}\int_0^{\infty} f(\xi)\sin(k\xi)\,d\xi \]
$$f(x)$$$$\hat{f}(k)$$
\[1\text{ if } -s < x < s, 0\text{ otherwise }\]\[ \sqrt{\frac{2}{\pi}}\frac{\sin(ks)}{k} \]
\[ \frac{1}{x^2 + s^2} \]\[ \frac{1}{s}\sqrt{\frac{\pi}{2}}e^{-s|k|} \]
\[ e^{-sx^2} \]\[ \frac{1}{\sqrt{2s}}e^{\frac{k^2}{4s}} \]
\[ \frac{\sin(sx)}{x}\]\[ \sqrt{\frac{\pi}{2}}\text{ if } |k|<s, 0\text{ otherwise} \]
\[ e^{isx}\text{ if } a < x < b, 0\text{ otherwise} \]\[ \frac{i}{\sqrt{2\pi}}\left(\frac{1}{s-k} \right)\left(e^{ea(s-k)} - e^{ib(s-k)} \right) \]


AMath 402 - Dynamical Systems and Chaos
Dimensionless time
\[ \tau = \frac{t}{T} \]
where T gets picked so that
\[\frac{}{}\]
and
\[\frac{}{}\]
are of order 1.
Fixed points of $$x'=f(x)$$: set $$f(x)=0$$ and solve for roots
Bifurcation: Given $$x'=f(x,r)$$, set $$f(x,r)=0$$ and solve for $$r$$, then plot $$r$$ on the $$x-axis$$ and $$x$$ on the $$y-axis$$.
Saddle Node
Saddle Node
Transcritical Node
Transcritical
Subcritical Pitchfork
Subcritical Pitchfork
Supercritical Pitchfork
Supercritical Pitchfork

\[ \begin{matrix} x'=ax+by \\ y'=cx+dy \end{matrix} \]
\[ A=\begin{bmatrix} a & b \\ c & d \end{bmatrix}\]
\[ \begin{vmatrix} a-\lambda & b \\ c & d-\lambda \end{vmatrix}=0 \]
\[ \begin{matrix} \lambda^2 - \tau\lambda + \delta=0 & \lambda = \frac{\tau \pm \sqrt{\tau^2 - 4\delta}}{2} \\ \tau = a+d & \delta=ad-bc \end{matrix} \]
\[ x(t)=c_1 e^{\lambda_1 t}v_1 + c_2 e^{\lambda_2 t}v_2 \]
$$v_1,v_2$$ are eigenvectors.
Given $$\tau = \lambda_1 + \lambda_2$$ and $$\delta=\lambda_1\lambda_2$$:
if $$\delta < 0$$, the eigenvalues are real with opposite signs, so the fixed point is a saddle point.
otherwise, if $$\tau^2-4\delta > 0$$, its a node. This node is stable if $$\tau < 0$$ and unstable if $$\tau > 0$$
if $$\tau^2-4\delta < 0$$, its a spiral, which is stable if $$\tau < 0$$, unstable if $$\tau > 0$$, or a center if $$\tau=0$$
if $$\tau^2-4\delta = 0$$, its degenerate.
\[ \begin{bmatrix} x'=f(x,y) \\ y'=g(x,y) \end{bmatrix} \]
Fixed points are found by solving for $$x'=0$$ and $$y'=0$$ at the same time.
nullclines are when either $$x'=0$$ or $$y'=0$$ and are drawn on the phase plane.
\[ \begin{bmatrix} \frac{\partial f}{\partial x} & \frac{\partial f}{\partial y} \\ \frac{\partial g}{\partial x} & \frac{\partial g}{\partial y} \end{bmatrix} \]


$$\leftarrow$$ For nonlinear equations, evaluate this matrix at each fixed point, then use the above linear classification scheme to classify the point.

A basin for a given fixed point is the area of all trajectories that eventually terminate at that fixed point.
Given $$x'=f(x)$$, $$E(x)$$ is a conserved quantity if $$\frac{dE}{dt}=0$$
A limit cycle is an isolated closed orbit in a nonlinear system. Limit cycles can only exist in nonlinear systems.
If a function can be written as $$\vec{x}'=-\nabla V$$, then its a gradient function and can't have closed orbits.
The Liapunov function $$V(x)$$ for a fixed point $$x^*$$ satisfies $$V(x) > 0 \forall x \neq x^*, V(x^*)=0, V' < 0 \forall x \neq x^*$$
A Hopf bifurcation occurs as the fixed points eigenvalues (in terms of $$\mu$$) cross the imaginary axis.

Math 300 - Introduction to Mathematical Reasoning
PQ$$P \Rightarrow Q$$$$\neg P \vee Q$$
TTTT
TFFF
FTTT
FFTT

All valid values of $$x$$ constitute the Domain.
$$f(x)=y$$ The range in which $$y$$ must fall is the codomain
The image is the set of $$y$$ values that are possible given all valid values of $$x$$
So, $$\frac{1}{x}$$ has a domain $$\mathbb{R} - \{0\}$$ and a codomain of $$\mathbb{R}$$. However, no value of $$x$$ can ever produce $$f(x)=0$$, so the Image is $$\mathbb{R}-\{0\}$$

Injective: No two values of $$x$$ yield the same result. $$f(x_1)\neq f(x_2)$$ if $$x_1 \neq x_2$$ for all $$x$$
Surjective: All values of $$y$$ in the codomain can be produced by $$f(x)$$. In other words, the codomain equals the image.
Bijective: A Bijective function is both Injective and Surjective - all values of $$y$$ are mapped to exactly one value of $$x$$. A simple way to prove this is to solve $$f(x)$$ for $$x$$. If this can be done without creating multiple solutions (a square root, for example, yields $$\pm$$, not a single answer), then it's a bijective function.
If $$f(x)$$ is a bijection, it is denumerable. Any set that is equivalent to the natural numbers is denumerable.
$$\forall x \in \mathbb{R}$$ means "for all $$x$$ in $$\mathbb{R}$$", where $$\mathbb{R}$$ can be replaced by any set.
$$\exists y \in \mathbb{R}$$ means "there exists a $$y$$ in $$\mathbb{R}$$", where $$\mathbb{R}$$ can be replaced by any set.
\[ A \vee B = A\text{ or }B \]
\[ A \wedge B = A\text{ and }B \]
\[ P \Leftrightarrow Q\text{ means }P \Rightarrow Q \wedge Q\Rightarrow P \text{ or } P\text{ iff }Q \text{ (if and only if)} \]

$$A \cup B$$ = Union - All elements that are in either A or B, or both.
\[ \{x|x \in A \text{ or } x \in B \} \]

$$A \cap B$$ = Intersection - All elements that are in both A and B
\[ \{x|x \in A \text{ and } x \in B \} \]

$$A\subseteq B$$ = Subset - Indicates A is a subset of B, meaning that all elements in A are also in B.
\[ \{x \in A \Rightarrow x \in B \} \]

$$A \subset B$$ = Strict Subset - Same as above, but does not allow A to be equal to B (which happens if A has all the elements of B, because then they are the exact same set).
$$A-B$$ = Difference - All elements in A that aren't also in B
\[ \{x|x \in A \text{ and } x \not\in B \} \]

$$A\times B$$ = Cartesian Product - All possible ordered pairs of the elements in both sets:
\[ \{(x,y)|x \in A\text{ and }y\in B\} \]

ProofWe use induction on $$n$$
Base Case:[Prove $$P(n_0)$$]
Inductive Step:Suppose now as inductive hypothesis that [$$P(k)$$ is true] for some integer $$k$$ such that $$k \ge n_0$$. Then [deduce that $$P(k+1)$$ is true]. This proves the inductive step.
Conclusion:Hence, by induction, [$$P(n)$$ is true] for all integers $$n \ge n_0$$.
ProofWe use strong induction on $$n$$
Base Case:[Prove $$P(n_0)$$, $$P(n_1)$$, ...]
Inductive Step:Suppose now as inductive hypothesis that [$$P(n)$$ is true for all $$n \le k$$] for some positive integer $$k$$, then [deduce that $$P(k+1)$$ is true]. This proves the inductive step.
Conclusion:Hence, by induction [$$P(n)$$ is true] for all positive integers $$n$$.
Proof:Suppose, for contradiction, that the statement $$P$$ is false. Then, [create a contradiction]. Hence our assumption that $$P$$ is false must be false. Thus, $$P$$ is true as required.

The composite of $$f:X\rightarrow Y$$ and $$g:Y\rightarrow Z$$ is $$g\circ f: x\rightarrow Z$$ or just $$gf: X\rightarrow Z$$. $$g\circ f = g(f(x)) \forall x \in X$$
\[ a\equiv b \bmod m \Leftrightarrow b\equiv a \bmod m \]
If
\[ a \equiv b \bmod m\text{ and }b \equiv c \bmod m,\text{ then }a \]

Negation of $$P \Rightarrow Q$$ is $$P \wedge (\neg Q)$$ or $$P and (not Q)$$
If $$m$$ is divisible by $$a$$, then $$a b_1 \equiv a b_2 \bmod m \Leftrightarrow b_1 \equiv b_2 \bmod\left(\frac{m}{a} \right)$$
Fermat's little theorem: If $$p$$ is a prime, and $$a \in \mathbb{Z}^+$$ which is not a multiple of $$p$$, then $$a^{p-1}\equiv 1 \bmod p$$.
Corollary 1: If $$p$$ is prime, then $$\forall a \in \mathbb{Z}, a^p = a \bmod p$$
Corollary 2: If $$p$$ is prime, then $$(p-1)! \equiv -1 \bmod p$$

Division theorem: $$a,b \in \mathbb{Z}$$, $$b > 0$$, then $$a = bq+r$$ where $$q,r$$ are unique integers, and $$0 \le r < b$$. Thus, for $$a=bq+r$$, $$\gcd(a,b)=\gcd(b,r)$$. Furthermore, $$b$$ divides $$a$$ if and only if $$r=0$$, and if $$b$$ divides $$a$$, $$\gcd(b,a)=b$$

Euclidean Algorithm: $$\gcd(136,96)$$
$$136=96\cdot 1 + 40$$
\[ 290x\equiv 5\bmod 357 \rightarrow 290x + 357y = 5 \]

$$96=40\cdot 2 + 16$$
\[ ax\equiv b \bmod c \rightarrow ax+cy=b \]

$$40=16\cdot 2 + 8$$
$$16=8\cdot 2 + 0 \leftarrow$$ stop here, since the remainder is now 0
$$\gcd(136,96)=8$$

Diophantine Equations (or linear combinations):
$$140m + 63n = 35$$ $$m,n \in \mathbb{Z}$$ exist for $$am+bn=c$$ iff $$\gcd(a,b)$$ divides $$c$$
$$140=140\cdot 1 + 63\cdot 0$$
$$63=140\cdot 0 + 63\cdot 1$$ dividing $$am+bn=c$$ by $$\gcd(a,b)$$ always yields coprime $$m$$ and $$n$$.
$$14=140\cdot 1 - 63\cdot 2$$
$$7=63\cdot 1 - 14\cdot 4 = 63 - (140\cdot 1 - 63\cdot 2)\cdot 4 = 63 - 140\cdot 4 + 63\cdot 8 = 63\cdot 9 - 140\cdot 4 $$
$$0=14 - 7\cdot 2 =140\cdot 1 - 63\cdot 2 - 2(63\cdot 9 - 140\cdot 4) = 140\cdot 9-63\cdot 20 $$
So $$m=9$$ and $$n=-20$$

Specific: $$7=63\cdot 9 - 140\cdot 4 \rightarrow 140\cdot(-4)+63\cdot 9=7\rightarrow 140\cdot(-20)+63\cdot45=35$$
So for $$140m+63n=35, m=-20, n=45$$
Homogeneous: $$140m+63n=0 \; \gcd(140,63)=7 \; 20m + 9n = 0 \rightarrow 29m=-9n$$
$$m=9q, n=-20q$$ for $$q\in \mathbb{Z}$$ or $$am+bn=0 \Leftrightarrow (m,n)=(bq,-aq)$$
General: To find all solutions to $$140m+63n=35$$, use the specific solution $$m=-20, n=45$$
$$140(m+20) + 63(n-45) = 0$$
$$(m+20,n-45)=(9q,-20q)$$ use the homogeneous result and set them equal.
$$(m,n)=(9q-20,-20q+45)$$ So $$m=9q-20$$ and $$n=-20q+45$$
\[ [a]_m = \{x\in \mathbb{Z}| x\equiv a \bmod m \} \Rightarrow \{ mq + a|q \in \mathbb{Z} \} \]

$$ax\equiv b \bmod m$$ has a unique solution $$\pmod{m}$$ if $$a$$ and $$m$$ are coprime. If $$\gcd(a,b)=1$$, then $$a$$ and $$b$$ are coprime. $$[a]_m$$ is invertible if $$\gcd(a,m)=0$$.

Math 327 - Introduction to Real Analysis I
Cauchy Sequence: For all $$\epsilon > 0$$ there exists an integer $$N$$ such that if $$n,m \ge N$$, then $$|a_n-a_m|<\epsilon$$

Alternating Series: Suppose the terms of the series $$\sum u_n$$ are alternately positive and negative, that $$|u_{n+1}| \le |u_n|$$ for all $$n$$, and that $$u_n \to 0$$ as $$n\to\infty$$. Then the series $$\sum u_n$$ is convergent.

Bolzano-Weierstrass Theorem: If $$S$$ is a bounded, infinite set, then there is at least one point of accumulation of $$S$$.

$$\sum u_n$$ is absolutely convergent if $$\sum|u_n|$$ is convergent
If $$\sum u_n$$ is absolutely convergent, then $$\sum u_n = \sum a_n - \sum b_n$$ where both $$\sum a_n$$ and $$\sum b_n$$ are convergent. If $$\sum u_n$$ is conditionally convergent, both $$\sum a_n$$ and $$\sum b_n$$ are divergent.

\[ \sum u_n = U = u_0 + u_1 + u_2 + ... \]
\[ w_0 = u_0 v_0 \]
\[ w_1 = u_0 v_1 + u_1 v_0 \]

\[ \sum v_n = V = v_0 + v_1 + v_2 + ... \]
\[ w_n = u_0 v_n + u_1 v_{n-1} + ... + u_n v_0 \]

\[ \sum w_n = UV = w_0 + w_1 + w_2 + ... \]
Provided
\[ \sum u_n, \sum v_n \]
are absolutely convergent.

$$\sum a_n x^n$$ is either absolutely convergent for all $$x$$, divergent for all $$x\neq 0$$, or absolutely convergent if $$-R < x < R$$ (it may or may not converge for $$x=\pm R$$ ).
$$-R < x < R$$ is the interval of convergence. $$R$$ is the radius of convergence.
\[ R=\lim_{n \to \infty}\left|\frac{a_n}{a_{n+1}}\right| \]
if the limit exists or is $$+\infty$$
Let the functions of the sequence $$f_n(x)$$ be defined on the interval $$[a,b]$$. If for each $$\epsilon > 0$$ there is an integer $$N$$ independent of x such that $$|f_n(x) - f_m(x)| < \epsilon$$ where $$N \le m,n$$.

You can't converge uniformly on any interval containing a discontinuity.
\[ |a|+|b|\le|a+b| \]
\[ \lim_{n \to \infty}(1+\frac{k}{n})^n = e^k \]
\[ lim_{n \to \infty} n^{\frac{1}{n}}=1 \]
\[ \sum_{k=0}^{\infty}=\frac{a}{1-r} \]
if $$|r| < 1$$
\[\sum a_n x^n\]
has a radius of convergence
\[R = \lim_{n \to \infty}\left|\frac{a_n}{a_{n+1}} \right|\]
if it exists or is $$+\infty$$. The interval of convergence is $$-R < x < R$$
\[ \sum^{\infty}\frac{x^2}{(1+x^2)^n} = x^2\sum\left(\frac{1}{1+x^2}\right)^n = x^2\left(\frac{1}{1-\frac{1}{1+x^2}}\right) = x^2\left( \frac{1+x^2}{1+x^2-1}\right) = x^2\left( \frac{1+x^2}{x^2} \right) = 1+x^2 \]

Math 427 - Complex Analysis
0$$\frac{\pi}{6}$$$$\frac{\pi}{4}$$$$\frac{\pi}{3}$$$$\frac{\pi}{2}$$
$$\sin$$0$$\frac{1}{2}$$$$\frac{\sqrt{2}}{2}$$$$\frac{\sqrt{3}}{2}$$1
$$\cos$$1$$\frac{\sqrt{3}}{2}$$$$\frac{\sqrt{2}}{2}$$$$\frac{1}{2}$$0
$$\tan$$0$$\frac{1}{\sqrt{3}}$$1$$\sqrt{3}$$$$\varnothing$$
\[ \frac{z_1}{z_2} = \frac{x_1 x_2 + y_1 y_2}{x_2^2 + y_2^2} + i\frac{y_1 x_1 - x_1 y_2}{x_2^2 + y_2^2} \]
\[ |z| = \sqrt{x^2 + y^2} \]
\[ \bar{z} = x-i y \]
\[ |\bar{z}|=|z| \]

\[ \text{Re}\,z=\frac{z+\bar{z}}{2} \]
\[ \text{Im}\,z=\frac{z-\bar{z}}{2i} \]
\[ \text{Arg}\,z=\theta\text{ for } -\pi < \theta < \pi \]
\[ z=re^{i\theta}=r(\cos(\theta) + i\sin(\theta)) \]

\[ \lim_{z \to z_0} f(z) = w_0 \iff \lim_{x,y \to x_0,y_0} u(x,y) = u_0 \text{ and }\lim_{x,y \to x_0,y_0} v(x,y)=v_0 \text{ where } w_0=u_0+iv_0 \text{ and } z_0=x_0+iy+0 \]

\[ \lim_{z \to z_0} f(z) = \infty \iff \lim_{z \to z_0} \frac{1}{f(z)}=0 \]

\[ \lim_{z \to \infty} f(z) = w_0 \iff \lim_{z \to 0} f\left(\frac{1}{z}\right)=w_0\]
\[ \text{Re}\,z\le |\text{Re}\,z|\le |z| \]
\[ \text{Im}\,z\le |\text{Im}\,z| \le z \]

\[ \lim_{z \to \infty} f(z) = \infty \iff \lim_{z\to 0}\frac{1}{f\left(\frac{1}{z}\right)}=0\]
\[ \left| |z_1| - |z_2| \right| \le |z_1 + z_2| \le |z_1| + |z_2| \]

Roots:
\[ z = \sqrt[n]{r_0} \exp\left[i\left(\frac{\theta_0}{n} + \frac{2k\pi}{n} \right)\right] \]
Harmonic:
\[ f_{xx} + f_{yy} = 0 \text{ or } f_{xx}=-f_{yy} \]

Cauchy-Riemann:
\[ f(z) = u(x,y)+iv(x,y) \]
\[ \sinh(z)=\frac{e^z-e^{-z}}{2}=-i\sin(iz) \]
\[ \frac{d}{dz}\sinh(z)=\cosh(z) \]

\[ u_x = v_y \]
\[ u_y = -v_x \]
\[ \cosh(z) = \frac{e^z + e^{-z}}{2} = cos(iz) \]
\[ \frac{d}{dz}\cosh(z)=\sinh(z) \]

\[ f(z) = u(r,\theta)+iv(r,\theta) \]
\[ \sin(z)=\frac{e^{iz}-e{-iz}}{2i}=i-\sinh(iz)=\sin(x)\cosh(y) + i\cos(x)\sinh(y) \]

\[ r u_r = v_{\theta} \]
\[ u_{\theta}=-r v_r \]
\[ \cos(z)=\frac{e^{iz}+e^{-iz}}{2}=\cosh(iz)=\cos(x)\cosh(y) - i \sin(x)\sinh(y) \]

\[ \sin(x)^2 + \sinh(y)^2 = 0 \]
\[ |\sin(z)|^2 = \sin(x)^2 + \sinh(y)^2 \]
\[ |\cos(z)|^2 = \cos(x)^2 + \sinh(y)^2 \]

$$e^z$$ and Log:
\[ e^z=e^{x+iy}=e^x e^{iy}=e^x(\cos(y) + i\sin(y)) \]
\[ e^x e^{iy} = \sqrt{2} e^{i\frac{\pi}{4}} \]
\[ e^x = \sqrt{2} \]
\[ y = \frac{\pi}{4} + 2k\pi \]
\[ x = \ln\sqrt{2} \]
So,
\[ z = \ln\sqrt{2} + i\pi\left(\frac{1}{4} + 2k\right) \]
\[ \frac{d}{dz} log(f(z)) = \frac{f'(z)}{f(z)} \]

Cauchy-Gourgat: If $$f(z)$$ is analytic at all points interior to and on a simple closed contour $$C$$, then
\[ \int_C f(z) \,dz=0 \]

\[ \int_C f(z) \,dz = \int_a^b f[z(t)] z'(t) \,dt \]
\[ a \le t \le b \]
$$z(t)$$ is a parameterization. Use $$e^{i\theta}$$ for circle!
Maximum Modulus Principle: If $$f(z)$$ is analytic and not constant in $$D$$, then $$|f(z)|$$ has no maximum value in $$D$$. That is, no point $$z_0$$ is in $$D$$ such that $$|f(z)| \le |f(z_0)|$$ for all $$z$$ in $$D$$.
Corollary: If $$f(z)$$ is continuous on a closed bounded region $$R$$ and analytic and not constant through the interior of $$R$$, then the maximum value of $$|f(z)|$$ in $$R$$ always exists on the boundary, never the interior.
Taylor's Theorem: Suppose $$f(z)$$ is analytic throughout a disk $$|z-z_0|<R$$. Then $$f(z)$$ has a power series of the form
\[ f(z) = \sum_{n=0}^{\infty}\frac{f^{(n)}(z_0)}{n!}(z-z_0)^n \]
where $$|z-z_0| < R_0$$ and $$n=0,1,2,...$$
Alternatively,
\[ \sum_{n=0}^{\infty} a_n(z-z_0)^n \text{ where } a_n=\frac{f^{(n)}(z_0)}{n!} \]

For $$|z|<\infty$$:
\[ e^z = \sum_{n=0}^{\infty}\frac{z^n}{n!} \]
\[ \sin(z) = \sum_{n=0}^{\infty}(-1)^n\frac{z^{2n+1}}{(2n+1)!} \]
\[ \cos(z) = \sum_{n=0}^{\infty}(-1)^n\frac{z^{2n}}{(2n)!} \]

Note that
\[ \frac{1}{1 - \frac{1}{z}}=\sum_{n=0}^{\infty}\left(\frac{1}{z}\right)^n \text{ for } \left|\frac{1}{z}\right| < 1\]
, which is really $$1 < |z|$$ or $$|z| > 1$$
For $$|z| < 1$$:
\[ \frac{1}{1-z} = \sum_{n=0}^{\infty} z^n \]
\[ \frac{1}{1+z} = \sum_{n=0}^{\infty} (-1)^n z^n \]
For $$|z-1|<1$$:
\[ \frac{1}{z} = \sum_{n=0}^{\infty} (-1)^n (z-1)^n \]

Analytic: $$f(z)$$ is analytic at point $$z_0$$ if it has a derivative at each point in some neighborhood of $$z_0$$.
$$f(z)=u(x,y)+iv(x,y)$$ is analytic if and only if $$v$$ is a harmonic conjugate of $$u$$.
If $$u(x,y)$$ and $$v(x,y)$$ are harmonic functions such that $$u_{xx}=-u{yy}$$ and $$v_{xx}=-v_{yy}$$, and they satisfy the Cauchy-Reimann conditions, then $$v$$ is a harmonic conjugate of $$u$$.

Differentiable: $$f(z)=u(x,y)+iv(x,y)$$ is differentiable at a point $$z_0$$ if $$f(z)$$ is defined within some neighborhood of $$z_0=x_0+iy_0$$, $$u_x$$ $$u_y$$ $$v_x$$ and $$v_y$$ exist everywhere in the neighborhood, those first-order partial derivatives exist at $$(x_0,y_0)$$ and satisfy the Reimann-Cauchy conditions at $$(x_0,y_0)$$.
Cauchy Integral Formula:
\[ \int_C \frac{f(z)}{z-z_0}\,dz = 2\pi i f(z_0) \]
where $$z_0$$ is any point interior to $$C$$ and $$f(z)$$ is analytic everywhere inside and on $$C$$ taken in the positive sense. Note that $$f(z)$$ here refers to the actual function $$f(z)$$, not $$\frac{f(z)}{z-z_0}$$
Generalized Cauchy Integral Formula:
\[ \int_C \frac{f(z)}{(z-z_0)^{n+1}}\,dz = \frac{2\pi i}{n!} f^{(n)}(z_0) \]
(same conditions as above)
Remember, discontinuities that are roots can be calculated and factored:
\[ \frac{1}{z^2-w_0}=\frac{1}{(z-z_1)(z-z_2)} \]

Residue at infinity:
\[ \def\res{\mathop{Res}\limits} \int_C f(z)\,dz = 2\pi i \,\res_{z=0}\left[\frac{1}{z^2} f\left(\frac{1}{z}\right) \right] \]

A residue at $$z_0$$ is the $$n=-1$$ term of the Laurent series centered at $$z_0$$.
A point $$z_0$$ is an isolated singular point if $$f(z_0)$$ fails to be analytic, but is analytic at some point in every neighborhood of $$z_0$$, and there's a deleted neighborhood $$0 < |z-z_0| < \epsilon$$ of $$z_0$$ throughout which $$f$$ is analytic.
\[ \res_{z=z_0}\,f(z)=\frac{p(z_0)}{q'(z_0)}\text{ where }f(z) = \frac{p(z)}{q(z)}\text{ and } p(z_0)\neq 0 \]

\[ \int_C f(z)\,dz = 2\pi i \sum_{k=1}^n\,\res_{z=z_k}\,f(z) \]
where $$z_0$$, $$z_1$$, $$z_2$$,... $$z_k$$ are all the singular points of $$f(z)$$ (which includes poles).

If a series has a finite number of $$(z-z_0)^{-n}$$ terms, its a pole ($$\frac{1}{z^4}$$ is a pole of order 3). If a function, when put into a series, has no $$z^{-n}$$ terms, it's a removable singularity. If it has an infinite number of $$z^{-n}$$ terms, its an essential singularity (meaning, you can't get rid of it).

AMath 401 - Vector Calculus and Complex Variables
$$||\vec{x}||=\sqrt{x_1^2+x_2^2+ ...}$$
$$\vec{u}\cdot\vec{v} = ||\vec{u}||\cdot||\vec{v}|| \cos(\theta)=u_1v_1+u_2v_2+ ...$$
$$||\vec{u}\times\vec{v}|| = ||\vec{u}||\cdot||\vec{v}|| \sin(\theta) = \text{ area of a parallelogram}$$
\[ \vec{u}\times\vec{v} = \begin{vmatrix} \vec{\imath} & \vec{\jmath} & \vec{k} \\ u_1 & u_2 & u_3 \\ v_1 & v_2 & v_3 \end{vmatrix} \]
\[ \begin{vmatrix} a & b \\ c & d \end{vmatrix} = ad-bc \]
\[ \vec{u}\cdot\vec{v}\times\vec{w} = \vec{u}\cdot(\vec{v}\times\vec{w})=\text{ volume of a parallelepiped} \]

\[ h_?\equiv\left|\left|\frac{\partial\vec{r}}{\partial ?}\right|\right| \]
\[ \hat{e}_r(\theta)=\frac{1}{h_r}\frac{\partial\vec{r}}{\partial r} \]
\[ \hat{e}_r'(\theta)=\frac{d\hat{e}_r}{d\theta}=\hat{e}_{\theta}(\theta) \]

\[ \vec{r}=r(t)\hat{e}_r(\theta(t)) \]
\[ \vec{r}'(t)=r'(t)\hat{e}_r + r(t)\frac{d\hat{e}_r}{dt}\]
\[ \vec{r}'(t)=r'(t)\hat{e}_r + r(t)\frac{d\hat{e}_r}{d\theta}\frac{d\theta}{dt}=r'(t)\hat{e}_r + r(t)\hat{e}_{\theta} \theta'(t) \]

Projection of $$\vec{u}$$ onto $$\vec{v}$$:
\[ ||\vec{u}|| \cos(\theta) = \frac{\vec{u}\cdot\vec{v}}{||\vec{v}||} \]
Arc Length:
\[ \int_a^b \left|\left| \frac{d\vec{r}}{dt} \right|\right| \,dt = \int_a^b ds \]

Parametrization:
\[ s(t) = \int_a^t \left|\left|\frac{d\vec{r}}{dt}\right|\right| \,dt \]
\[ \frac{dx}{dt}=x'(t) \]
\[ dx = x'(t)\,dt \]
\[ \oint x \,dy - y \,dx = \oint\left(x \frac{dy}{dt} - y \frac{dx}{dt}\right)\,dt = \oint x y'(t) - y x'(t) \,dt \]
\[ \nabla = \frac{\partial}{\partial x}\vec{\imath} + \frac{\partial}{\partial y}\vec{\jmath} + \frac{\partial}{\partial z}\vec{k} \]
\[ \nabla f = \left\langle \frac{\partial f}{\partial x},\frac{\partial f}{\partial y},\frac{\partial f}{\partial z} \right\rangle \]
\[ D_{\vec{u}} f(\vec{P})=f'_{\vec{u}}=\nabla f \cdot \vec{u} \]
\[ \nabla(fg)=f\nabla g + g \nabla f \]

\[ \vec{F}(x,y,z)=F_1(x,y,z)\vec{\imath} + F_2(x,y,z)\vec{\jmath} + F_3(x,y,z)\vec{k} \]

\[ \text{div}\, \vec{F} = \nabla \cdot \vec{F} = \frac{\partial F_1}{\partial x} + \frac{\partial F_2}{\partial y} + \frac{\partial F_3}{\partial z} \]

\[ \text{curl}\, \vec{F} = \nabla \times \vec{F} = \left\langle \frac{\partial F_3}{\partial y} - \frac{\partial F_2}{\partial z}, \frac{\partial F_1}{\partial z} - \frac{\partial F_3}{\partial x}, \frac{\partial F_2}{\partial x} - \frac{\partial F_1}{\partial y} \right\rangle \]

Line integral:
\[ \int_{\vec{r}(a)}^{\vec{r}(b)}\vec{F}\cdot \vec{r}'(t)\,dt = \int_{\vec{r}(a)}^{\vec{r}(b)}\vec{F}\cdot d\vec{r} \]
Closed path:
\[ \oint \vec{F}\cdot d\vec{r} \]
\[ d\vec{r} = \nabla\vec{r}\cdot \langle du_1,du_2,du_3 \rangle = h_1 du_1 \hat{e}_1 + h_2 du_2 \hat{e}_2 + h_3 du_3 \hat{e}_3 \]
\[ h_?= \left|\left| \frac{\partial\vec{r}}{\partial ?} \right|\right| = \frac{1}{||\partial ?||} \]
\[ \hat{e}_?=\frac{1}{h_?}\frac{\partial\vec{r}}{\partial?}=h_?\nabla?(x,y,z)=\frac{\nabla?}{||\nabla?||} \]
If $$\vec{r}=\vec{r}(s)$$ then
\[ \int_a^b\vec{F}\cdot \frac{d\vec{r}}{ds} \,ds = \int_a^b\vec{F}\cdot\vec{T} \,ds\]

\[ \nabla f \cdot \hat{e}_?=\frac{1}{h_?}\frac{\partial f}{\partial ?} \]
\[ \nabla f = (\nabla f \cdot \hat{e}_r)\hat{e}_r + (\nabla f \cdot \hat{e}_{\theta})\hat{e}_{\theta} = \frac{\partial f}{\partial r}\hat{e}_r + \frac{1}{r}\frac{\partial f}{\partial \theta}\hat{e}_{\theta} \]
\[ ds = \sqrt{d\vec{r}\cdot d\vec{r}} = \left|\left| \frac{d\vec{r}}{dt}dt \right|\right| = \sqrt{h_1^2 du_1^2 + h_2^2 du_2^2+h_3^2 du_3^2} \]

\[ Spherical: h_r=1, h_{\theta}=r, h_{\phi}=r\sin(\theta) \]

\[ \vec{r}=\frac{\nabla f}{||\nabla f||} \]
\[ \vec{r}=\vec{r}(u,v) \]
\[ \vec{n}= \frac{\frac{\partial\vec{r}}{\partial u}\times\frac{\partial\vec{r}}{\partial v}}{\left|\left| \frac{\partial\vec{r}}{\partial u}\times\frac{\partial\vec{r}}{\partial v} \right|\right|} \]

$$\vec{F}$$ is conservative if:
\[ \vec{F}=\nabla\phi \]
\[ \nabla\times\vec{F}=0 \]
\[ \vec{F}=\nabla\phi \iff \nabla\times\vec{F}=0 \]

\[ \iint\vec{F}\cdot d\vec{S} \]
\[ d\vec{S}=\left(\frac{\partial\vec{r}}{\partial u} \times \frac{\partial\vec{r}}{\partial v} \right)\,du\,dv \]
\[ d\vec{S}=\vec{n}\,dS \]
Surface Area:
\[ \iint \,dS \]

Flux:
\[ \iint\vec{F}\cdot d\vec{S} \]

Shell mass:
\[ \iint p\cdot dS \]

Stokes:
\[ \iint(\nabla\times\vec{F})\cdot d\vec{S} = \oint\vec{F}\cdot d\vec{r} \]

Divergence:
\[ \iiint\limits_V\nabla\cdot\vec{F}\,dV=\iint\limits_{\partial v} \vec{F}\cdot d\vec{S} \]

If $$z=f(x,y)$$, then
\[ \vec{r}(x,y) = \langle x,y,f(x,y) \rangle \]

\[ \nabla\cdot\vec{F}=\frac{1}{h_1 h_2 h_3}\left[\frac{\partial}{\partial u_1}(F_1 h_2 h_3) + \frac{\partial}{\partial u_2}(F_2 h_1 h_3) + \frac{\partial}{\partial u_3}(F_3 h_1 h_2) \right] \]
\[ dV = \left| \frac{\partial\vec{r}}{\partial u_1}\cdot\left(\frac{\partial\vec{r}}{\partial u_2}\times\frac{\partial\vec{r}}{\partial u_3} \right) \right| du_1 du_2 du_3 \]
If orthogonal,
\[ I = \iiint\limits_V f(u_1,u_2,u_3)h_1 h_2 h_3\,du_1\,du_2\,du_3 \]
\[ (x-c_x)^2 + (y-c_y)^2 = r^2 \Rightarrow \vec{r}(t)=\langle c_x + r\cos(t),c_y+r\sin(t) \rangle \]

Ellipse:
\[ \Rightarrow \vec{r}(t)=\langle c_x+a\cos(t), c_y+b\sin(t) \rangle \]

For spherical, if $$\theta$$ is innermost, its max value is $$\pi$$, or if its on the z value.
\[ \vec{r}(\theta,\phi)=\langle \sin(\theta)\cos(\phi), \sin(\theta)\sin(\phi),\cos(\theta) \rangle \]


Laplace Transform:
\[ \mathcal{L}\left[f(t)\right]=F(s)=\int_0^{\infty}e^{-st}f(t)\,dt \]
\[ \mathcal{L}[f'(t)] = s\mathcal{L}[f(t)] - f(0) = s\cdot F(s)-f(0)\]
\[ \mathcal{L}[f''(t)] = s^2\mathcal{L}[f(t)] - s\cdot f(0) - f'(0) = s^2\cdot F(s) - s\cdot f(0) - f'(0)\]

\[ \mathcal{L}[0] = 0 \]
\[ \mathcal{L}[1] = \frac{1}{s} \]
\[ \mathcal{L}[k] = \frac{k}{s} \]
\[ \mathcal{L}[e^{at}] = \frac{1}{s-a} \]
\[ \mathcal{L}[\cos(\omega t)] = \frac{s}{s^2 + \omega^2} \]
\[ \mathcal{L}[\sin(\omega t)] = \frac{\omega}{s^2 + \omega^2} \]


Math 461 - Combinatorial Theory I
General Pigeon: Let $$n$$,$$m$$, and $$r$$ be positive integers so that $$n>rm$$. Let us distribute $$n$$ balls into $$m$$ boxes. Then there will be at least 1 box in which we place at least $$r+1$$ balls.



Base Case:Prove $$P(0)$$ or $$P(1)$$
Inductive Step:Show that by assuming the inductive hypothesis $$P(k)$$, this implies that $$P(k+1)$$ must be true.
Strong Induction:Show that $$P(k+1)$$ is true if $$P(n)$$ for all $$n < k+1$$ is true.

There are $$n!$$ permutations of an $$n$$-element set (or $$n!$$ linear orderings of $$n$$ objects)
$$n$$ objects sorted into $$a,b,c,...$$ groups have $$\frac{n!}{a!b!c!...}$$ permutations. This is also known as a $$k$$-element multiset of $$n$$.
Number of $$k$$-digit strings in an $$n$$-element alphabet: $$n^k$$. All subsets of an $$n$$-element set: $$2^n$$
Let $$n$$ and $$k$$ be positive integers such that $$n \ge k$$, then the number of $$k$$-digit strings over an $$n$$-element alphabet where no letter is used more than once is $$\frac{n!}{(n-k)!}=(n)_k$$
\[ \binom{n}{k} = \frac{n!}{k!(n-k)!} = \frac{(n)_k}{k!} \rightarrow \]
This is the number of $$k$$-element subsets in $$[n]$$, where $$[n]$$ is an $$n$$-element set.
\[ \binom{n}{k} = \binom{n}{n-k} \]
\[ \binom{n}{0} = \binom{n}{n} = \binom{0}{0} = 1 \]

Number of $$k$$-element multisets in $$[n]$$:
\[ \binom{n+k-1}{k} \]

Binomial Theorem:
\[ (x+y)^n = \sum_{k=0}^n\binom{n}{k}x^k y^{n-k} \text{ for } n \ge 0 \]

Multinomial Theorem:
\[ (x_1 + x_2 + ... + x_k)^n = \sum_{a_1,a_2,...,a_k} \binom{n}{a_1,a_2,...,a_k} x_1^{a_1} x_2^{a_2} ... x_k^{a_k} \]
\[ \binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1} \text{ for } n,k \ge 0 \]
\[ \binom{k}{k} + \binom{k+1}{k} + ... + \binom{n}{k} = \binom{n+1}{k+1} \text{ for } n,k \ge 0 \]
\[ \binom{n}{k} \le \binom{n}{k} \text{ if and only if } k \le \frac{n-1}{2} \text{ and } n=2k+1 \]
\[ \binom{n}{k} \ge \binom{n}{k} \text{ if and only if } k \ge \frac{n-1}{2} \text{ and } n=2k+1 \]
\[ \binom{n}{a_1,a_2,...,a_k} = \frac{n!}{a_1!a_2!...a_k!} \]
\[ \binom{n}{a_1,a_2,...,a_k} = \binom{n}{a_1}\cdot \binom{n-a_1}{a_2} \cdot ... \cdot \binom{n-a_1-a_2-...-a_{k-1}}{a_k} \text{ if and only if } n=\sum_{i=1}^k a_i\]
\[ \binom{m}{k} = \frac{m(m-1)...(m-k+1)}{k!} \text{ for any real number } m \]
\[ (1+x)^m = \sum_{n\ge 0}^{\infty} \binom{m}{n}x^n \]
\[ \sum_{k=0}^n (-1)^k\binom{n}{k} = 0 \text{ for } n \ge 0 \]
\[ 2^n = \sum_{k=0}^n \binom{n}{k} = 0 \text{ for } n \ge 0 \]
\[ \sum_{k=1}^n k\binom{n}{k} = n 2^{n-1} \text{ for } n \ge 0 \]
\[ \binom{n+m}{k} = \sum_{i=0}^k \binom{n}{i} \binom{n}{k-i} \text{ for } n,m,k \ge 0 \]

\[ |E| = \frac{1}{2}\sum_{v\in V} deg(v) \]
or, the number of edges in a graph is half the sum of its vertex degrees.
Compositions:$$n$$ identical objects
$$k$$ distinct boxes
\[\binom{n-1}{k-1}\]$$n$$ identical objects
any number of distinct boxes
$$2^{n-1}$$
Weak Compositions:
(empty boxes allowed)
$$n$$ identical objects
$$k$$ distinct boxes
\[ \binom{n+k-1}{k-1} \]$$n$$ distinct objects
$$k$$ distinct boxes
$$k^n$$

Split $$n$$ people into $$k$$ groups of $$\frac{n}{k}$$:
Unordered:
\[ \frac{n!}{\left(\left(\frac{n}{k}\right)!\right)^k k!} \]
Ordered:
\[ \frac{n!}{\left(\left(\frac{n}{k}\right)!\right)^k} \]

Steps from (0,0) to (n,k) on a lattice:
\[\binom{n+k}{k}\]

Ways to roll $$n$$ dice so all numbers 1-6 show up at least once: $$6^n - \binom{6}{5}5^n + \binom{6}{4}4^n + \binom{6}{3}3^n + \binom{6}{2}2^n + \binom{6}{1}$$
The Sieve: $$|A_1| + |A_2| - |A_1\cap A_2|$$ or $$|A_1| + |A_2| + |A_3| - |A_1\cap A_2| - |A_1\cap A_3| - |A_2\cap A_3| + |A_1\cap A_2\cap A_3|$$
Also, $$|S - (S_A\cap S_B\cap S_C)| = |S| - |S_A| - |S_B| - |S_C| + |S_A\cap S_B| + |S_A\cap S_C| + |S_B\cap S_C| - |S_A\cap S_B\cap S_C|$$

Graphs: A simple graph has no loops (edges connecting a vertex to itself) or multiple edges between the same vertices. A walk is a path through a series of connected edges. A trail is a walk where no edge is traveled on more than once. A closed trail starts and stops on the same vertex. A Eulerian trail uses all edges in a graph. A trail that doesn't touch a vertex more than once is a path. $$K_n$$ is the complete graph on $$n$$-vertices.
If one can reach any vertex from any other on a graph $$G$$, then $$G$$ is a connected graph.
A connected graph has a closed Eulerian trail if and only if all its vertices have even degree. Otherwise, it has a Eulerian trail starting on S and ending on T if only S and T have odd degree.
In a graph without loops there are an even number of vertices of odd-degree. A cycle touches all vertices only once, except for the vertex it starts and ends on. A Hamiltonian cycle touches all vertices on a graph.
Let $$G$$ be a graph on $$n \ge 3$$ vertices, then $$G$$ has a Hamiltonian cycle if all vertices in $$G$$ have degree equal or greater than $$n/2$$. A complete graph $$K_n$$ has $$\binom{n}{k}\frac{(k-1)!}{2}$$ cycles of $$k$$-vertices.
Total Cycles:
\[ \sum_{k=3}^n\binom{n}{k}\frac{(k-1)!}{2} \]
Hamiltonian cycles:
\[ \frac{(n-1)!}{2} \]

Two graphs are the same if for any pair of vertices, the number of edges connecting them is the same in both graphs. If this holds when they are unlabeled, they are isomorphic.
A Tree is a minimally connected graph: Removing any edge yields a disconnected graph. Trees have no cycles, so any connected graph with no cycles is a tree.
All trees on $$n$$ vertices have $$n-1$$ edges, so any connected graph with $$n-1$$ edges is a tree.
Let $$T$$ be a tree on $$n \ge 2$$ vertices, then T has at least two vertices of degree 1.
Let $$F$$ be a forest on $$n$$ vertices with $$k$$ trees. Then F has $$n-k$$ edges.
Cayley's formula: The number of all trees with vertex set $$[n]$$ is $$A_n = n^{n-2}$$
A connected graph $$G$$ can be drawn on a plane so that no two edges intersect, then G is a planar graph.
A connected planar graph or convex polyhedron satisfies: Vertices + Faces = Edges + 2
$$K_{3,3}$$ and $$K_5$$ are not planar, nor is any graph with a subgraph that is edge-equivalent to them.
A convex Polyhedron with V vertices, E edges, and F faces satisfies: $$3F \le 3E$$, $$3V \le 3E$$, $$E \le 3V-6$$, $$E \le 3F-6$$, one face has at most 5 edges, and one vertex has at most degree 5.
$$K_{3,3}$$ has 6 vertices and 9 edges
A graph on $$n$$-vertices has $$\binom{n}{2}$$ possible edges.
If a graph is planar, then $$E \le 3V - 6$$. However, some non-planar graphs, like $$K_{3,3}$$, satisfy this too.
Prüfer code: Remove the smallest vertex from the graph, write down only its neighbor's value, repeat.

Math 462 - Combinatorial Theory II
All labeled graphs on $$n$$ vertices:
\[ 2^{\binom{n}{2}} \]

There are $$(n-1)!$$ ways to arrange $$n$$ elements in a cycle.
Given $$h_n=3 h_{n-1} - 2 h_{n-2}$$, change to $$h_{n+2}=3 h_{n+1} - 2 h_n$$, then $$h_{n+2}$$ is $$n=2$$ so multiply by $$x^{n+2}$$
\[ \sum h_{n+2}x^{n+2} = 3 \sum h_{n+1}x^{n+2} - 2 \sum h_n x^{n+2} \]
Then normalize to
\[ \sum_{n=2}^{\infty}h_n x^n \]
by subtracting $$h_0$$ and $$h_1$$
\[ \sum h_n x^n - x h_1 - h_0 = 3 x \sum h_{n+1}x^{n+1} - 2 x^2 \sum h_n x^n \]

\[ G(x) - x h_1 - h_0 = 3 x (G(x)-h_0) - 2 x^2 G(x) \]
Solve for:
\[ G(x) = \frac{1-x}{2x^2-3x+1} = \frac{1}{1-2x} = \sum (2x)^n \]

\[ G(x) = \sum(2x)^n = \sum 2^n x^n = \sum h_n x^n \rightarrow h_n=2^n \]

\[ \sum_{n=0}^{\infty} \frac{x^n}{n!} = e^x \]
\[ \sum_{n=0}^{\infty} (cx)^n = \frac{1}{1-cx} \]

Also,
\[ 2e_1 + 5e_2 = n \rightarrow \sum h_n x^n = \sum x^{2e_1+5e_2} = \sum x^{2e_1} x^{5e_2} = \left(\sum^{\infty} x^{2e_1}\right)\left(\sum^{\infty} x^{5e_2}\right)=\frac{1}{(1-x^2)(1-x^5)}\]


$$S(n,k)$$: A Stirling number of the second kind is the number of nonempty partitions of $$[n]$$ into k blocks where the order of the blocks doesn't matter. $$S(n,k)=S(n-1,k-1)+k S(n-1,k)$$, $$S(n,n-2) = \binom{n}{3} + \frac{1}{2}\binom{k}{2}\binom{n+2}{2}$$
Bell Numbers:
\[ B(n) = \sum_{i=0}^n S(n,i) \]
, or the number of all partitions of $$[n]$$ into nonempty parts (order doesn't matter).
Catalan Number $$C_n$$:
\[ \frac{1}{n+1}\binom{2n}{n} \]
derived from
\[ \sum_{n \ge 1} c_{n-1} x^n = x C(x) \rightarrow C(x) - 1 = x C(x)\cdot C(x) \rightarrow C(x) = \frac{1 - \sqrt{1-4x}}{2x} \]

Products: Let $$A(n) = \sum a_n x^n$$ and $$B(n) = \sum b_n x^n$$. Then $$A(x)B(x)=C(x)=\sum c_n x^n$$ where
\[ c_n = \sum_{i=0}^n a_i b_{n-i} \]


Cycles: The number of $$n$$-permuatations with $$a_i$$ cycles of length $$i \in [n]$$ is \frac{n!}{a_1!a_2!...a_n!1^{a_1}2^{a_2}...n^{a_n}}
The number of n-permutations with only one cycle is $$(n-1)!$$
$$c(n,k)$$: The number of $$n$$-permutations with $$k$$-cycles is called a signless stirling number of the first kind.
$$c(n,k) = c(n-1,k-1) + (n-1) c(n-1,k)$$
\[ c(n,n-2)= 2\binom{n}{3} + \frac{1}{2}\binom{n}{2}\binom{n-2}{2} \]

$$s(n,k) = (-1)^{n-k} c(n,k)$$ and is called a signed stirling number of the first kind.

Let $$i \in [n]$$, then fro all $$k \in [n]$$, there are $$(n-1)!$$ permutations that contain $$i$$ in a $$k$$-cycle.

\[ T(n,k)=\frac{k-1}{2k}n^2 - \frac{r(k-r)}{2k} \]
Let Graph $$G$$ have $$n$$ vertices and more than $$T(n,k)$$ edges. Then $$G$$ contains a $$K_{k+1}$$ subgraph, and is therefore not $$k$$-colorable.

$$N(T)$$ = all neighbors of the set of vertices $$T$$
$$a_{s,d} = \{ s,s+d,s+2d,...,s+(n-1)d \}$$
$$\chi(H)$$: Chromatic number of Graph $$H$$, or the smallest integer $$k$$ for which $$H$$ is $$k$$-colorable.
A 2-colorable graph is bipartite and can divide its vertices into two disjoint sets.
A graph is bipartite if and only if it does not contain a cycle of odd length.
A bipartite graph has at most $$\frac{n^2}{4}$$ edges if $$n$$ is even, and at most $$\frac{n^2 - 1}{4}$$ edges if $$n$$ is odd.
If graph $$G$$ is not an odd cycle nor complete, then $$\chi(G) \le$$ the largest vertex degree $$\ge 3$$.
A bipartite graph on $$n$$ vertices with a max degree of $$k$$ has at most $$k\cdot (n-k)$$ edges.
A tree is always bipartite (2-colorable).

Philip Hall's Theorem: Let a bipartite graph $$G=(X,Y)$$. Then $$X$$ has a perfect matching to $$Y$$ if and only if for all $$T \subset X, |T| \le |N(T)|$$

$$R(k,l):$$ The Ramsey Number $$R(k,l)$$ is the smallest integer such that any 2-coloring of a complete graph on $$R(k,l)$$ vertices will contain a red $$k$$-clique or blue $$l$$-clique. A $$k$$-clique is a complete subgraph on $$k$$ vertices.
\[ R(k,l) \le R(k,l-1) + R(k-1,l) \]
\[ R(k,k) \le 4^{k-1} \]
\[ R(k,l) \le \binom{k+l-2}{l-1} \]


Let $$P$$ be a partially ordered set (a "poset"), then:
1) $$\le$$ is reflexive, so $$x \le x$$ for all $$x \in P$$
2) $$\le$$ is transitive, so that if $$x \le y$$ and $$y \le z$$ then $$x \le z$$
3) $$\le$$ is anti-symmetric, such that if $$x\le y$$ and $$y \le x$$, then $$x=y$$

Let $$P$$ be the set of all subsets of $$[n]$$, and let $$A \le B$$ if $$A \subset B$$. Then this forms a partially ordered set $$B_n$$, or a Boolean Algebra of degree $$n$$.

\[ E(X)=\sum_{i \in S} i\cdot P(X=i) \]

A chain is a set with no two incomparable elements. An antichain has no comparable elements.
Real numbers are a chain. $$\{ (2,3), (1,3), (3,4), (2,4) \}$$ is an antichain in $$B_4$$, since no set contains another.
Dilworth: In a finite partially ordered set $$P$$, the size of any maximum antichain is equal to the number of chains in any chain cover.

Weak composition of n into 4 parts: $$a_1 + a_2 + a_3 + a_4 = n$$
Applying these rules to the above equation: $$a_1 \le 2, a_2\text{ mod }2 \equiv 0, a_3\text{ mod }2 \equiv 1, a_3 \le 7, a_4 \ge 1$$
Yields the following:
\[ a_1 + 2a_2 + (2a_3 + 1) + a_4 = n \]
\[(\sum_0^2 x^{a_1})(\sum_0^{\infty} x^{2a_2})(\sum_0^3 x^{2a_3 + 1})(\sum_1^{\infty} x^{a_4})=\frac{1+x+x^2}{1-x^2}(x+x^3+x^5+x^7)\left(\frac{1}{1-x} - 1\right)\]


Math 394 - Probability I
both E and F:
\[ P(EF) = P(E\cap F) \]
If E and F are independent, then
\[ P(E\cap F) = P(E)P(F) \]


$$P(F) = P(E) + P(E^c F)$$ $$P(E\cup F) = P(E) + P(F) - P(EF)$$
$$P(E\cup F \cup G) = P(E) + P(F) + P(G) - P(EF) - P(EG) - P(FG) + P(EFG)$$

E occurs given F:
\[P(E|F)=\frac{P(EF)}{P(F)} \]
$$P(EF)=P(FE)=P(E)P(F|E)$$
Bayes formula:
\[ P(E)=P(EF)+P(EF^c) \]
\[P(E)=P(E|F)P(F) + P(E|F^c)P(F^c) \]
\[P(E)=P(E|F)P(F) + P(E|F^c)[1 - P(F)] \]

\[ P(B|A)=P(A|B)\frac{P(B)}{P(A)} \]

The odds of A:
\[ \frac{P(A)}{P(A^c)} = \frac{P(A)}{1-P(A)} \]
\[P[\text{Exactly } k \text{ successes}]=\binom{n}{k}p^k(1-p)^{n-k} \]

\[ P(n \text{ successes followed by } m \text{ failures}) = \frac{p^{n-1}(1-q^m)}{p^{n-1}+q^{m-1}-p^{n-1}q^{m-1}} \]
where $$p$$ is the probability of success, and $$q=1-p$$ for failure.

\[ \sum_{i=1}^{\infty}p(x_i)=1 \]
where $$x_i$$ is the $$i^{\text{th}}$$ value that $$X$$ can take on.
\[ E[X] = \sum_{x:p(x) > 0}x p(x) \text{ or }\sum_{i=1}^{\infty} x_i p(x_i) \]
\[ E[g(x)]=\sum_i g(x_i)p(x_i) \]
\[ E[X^2] = \sum_i x_i^2 p(x_i) \]

\[ Var(X) = E[X^2] - (E[X])^2 \]
\[ Var(aX+b) = a^2 Var(X) \]
for constant $$a,b$$
\[ SD(X) = \sqrt{Var(X)} \]


Binomial random variable $$(n,p)$$:
\[ p(i)=\binom{n}{i}p^i(1-p)^{n-i}\; i=0,1,...,n\]
where $$p$$ is the probability of success and $$n$$ is the number of trials.
Poisson:
\[ E[X] = np \]
\[ E[X^2] = \lambda(\lambda + 1) \]
\[ Var(X)=\lambda \]
\[ P[N(t)=k)] = e^{-\lambda t}\frac{(\lambda t)^k}{k!} \: k=0,1,2,... \]
where $$N(t)=[s,s+t]$$
\[ E[X] = \int_{-\infty}^{\infty} x f(x) \,dx \]
\[ P\{X \le a \} = F(a) = \int_{-\infty}^a f(x) \,dx \]
\[ \frac{d}{da} F(g(a))=g'(a)f(g(a))\]
\[ E[g(X)]=\int_{-\infty}^{\infty} g(x) f(x) \,dx \]
\[ P\{ a \le X \le b \} = \int_a^b f(x) \,dx \]

Uniform:
\[ f(x) = \frac{1}{b-a} \text{ for } a\le x \le b \]
\[ E[X] = \frac{a+b}{2} \]
\[ Var(X) = \frac{(b-a)^2}{12}\]

Normal:
\[ f(x) = \frac{1}{\sqrt{2\pi} \sigma} e^{-\frac{(x-\mu)^2}{2\sigma^2}} \text{ for } -\infty \le x \le \infty \]
\[ E[X] = \mu \]
\[ Var(X) = \sigma^2 \]
\[ Z = \frac{X-\mu}{\sigma} \]

\[ P\left[a \le X \le b\right] = P\left[ \frac{a - \mu}{\sigma} < \frac{X - \mu}{\sigma} < \frac{b - \mu}{\sigma}\right] = \phi\left(\frac{b-\mu}{\sigma}\right) - \phi\left(\frac{a-\mu}{\sigma}\right) \]



\[ \phi(x) = GRAPH \]
\[ P[X \le a]=\phi\left(\frac{a-\mu}{\sigma}\right) \]
\[ P[Z > x] = P[Z \le -x] \]
\[ \phi(-x)=1-\phi(x) \]

\[ Y=f(X) \]
\[ F_Y=P[Y\le a]= P[f(X) \le a] = P[X \le f^{-1}(a)]=F_x(f^{-1}(a)) \]
\[ f_Y=\frac{d}{da}(f^{-1}(a))f_x(f^{-1}(a)) \]
\[ Y = X^2 \]
\[ F_Y = P[Y \le a] = P[X^2 \le a] = P[-\sqrt{a} \le X \le \sqrt{a}] = \int_{-\sqrt{a}}^{\sqrt{a}} f_X(x) dx \]
\[ f_Y = \frac{d}{da}(F_Y) \]


\[N(k) \ge x \rightarrow 1 - N(k) < x \]
\[ P(A \cap N(k) \ge x) = P(A) - P(A \cap N(k) < x) \]




Discrete:
\[ P(X=1) = P(X \le 1) - P(X < 1) \]
Continuous:
\[ P(X \le 1) = P(X < 1) \]


Exponential:
\[ f(x) = \lambda e^{-\lambda x} \text{ for } x \ge 0 \]
\[ E[X] = \frac{1}{\lambda} \]
\[ Var(X) = \frac{1}{\lambda^2} \]


Gamma:
\[ f(x) = \frac{\lambda e^{-\lambda x} (\lambda x)^{\alpha - 1}}{\Gamma(\alpha)} \]
\[ \Gamma(\alpha)=\int_0^{\infty} e^{-x}x^{\alpha-1} \,dx \]
\[ E[X] = \frac{\alpha}{\lambda} \]
\[ Var(X) = \frac{\alpha}{\lambda^2} \]

\[ E[X_iX_j] = P(X_i = k \cap X_j=k) = P(X_i = k)P(X_j = k|X_i=k) \]


Stat 390 - Probability and Statistics for Engineers and Scientists
\[ p(x) = \text{categorical (discrete)} \]
\[ f(x) = \text{continuous} \]
$$\mu_x=E[x]$$$$\sigma_x^2 = V[x]$$
Binomial$$n\pi$$$$n\pi (1-\pi)$$
Normal$$\mu$$$$\sigma^2$$
Poisson$$\lambda$$$$\lambda$$
Exponential$$\frac{1}{\lambda}$$$$\frac{1}{\lambda^2}$$
Uniform$$\frac{b+a}{2}$$$$\frac{(b-a)^2}{12}$$
Binomial\[ p(x) = \binom{n}{x} \pi^x (1 - \pi)^{n-x}\]
Poisson\[ p(x) = \frac{e^{-\lambda} \lambda^x}{x!} \]
Normal\[ f(x) = \frac{1}{\sqrt{2 \pi \sigma^2}} e^{-\frac{1}{2} \left(\frac{x - \mu}{\sigma} \right)}\]
Exponential\[ f(x) = \lambda e^{-\lambda x} \]
Uniform\[ f(x) = \frac{1}{b-a}\]
$$\pi = p =$$ proportion
$$n\pi = C = \lambda =$$ mean
$$\mu = n \pi$$
$$\sigma^2 = n \pi (1 - \pi)$$
Sample mean: $$\bar{x} =$$\[ \frac{1}{n} \sum_{i=1}^n x_i \]Sample median:\[\tilde{x} = \text{if } n \text{ is odd,} \left(\frac{n+1}{2}\right)^{\text{th}} \text{ value} \] \[ \text{if } n \text{ is even, average} \frac{n}{2} \text{ and } \frac{n}{2}+1\]
Sample variance:\[s^2 = \frac{1}{n-1}\sum (x_i - \bar{x})^2 = \frac{S_{xx}}{n-1} = \sum x_i^2 - \frac{1}{n} \left( \sum x_i \right)^2\]Standard deviation: $$s = \sqrt{s^2}$$

low/high quartile: median of lower/upper half of data. If $$n$$ is odd, include median in both.
low = 1st quartilehigh = 3rd quartilemedian = 2nd quartile

IQR: high - low quartiles
range: max - min
Total of something: $$\bar{x} n$$
An outlier is any data point outside the range defined by IQR $$\cdot 1.5$$
An extreme is any data point outside the range defined by IQR $$\cdot 3$$

\[ \mu_{\bar{x}} = \mu = \bar{x} \]
\[ \sigma_{\bar{x}} = \frac{\sigma}{\sqrt{n}} \]
\[ \mu_p = p = \pi \]
\[ \sigma_p = \sqrt{\frac{p(1-p)}{n}} \]

$$p(x)$$ distribution
[discrete]
mean: $$\mu_x = \sum x \cdot p(x) = E[x]$$
variance: $$\sigma_x^2 = \sum(x-\mu_x)^2 p(x) = V[x]$$
$$f(x)$$ distribution
[continuous]
mean:
\[ \mu_x = \int_{-\infty}^{\infty} x \cdot f(x) \]

median:
\[ \tilde{\mu} \rightarrow \int_{-\infty}^{\tilde{\mu}} f(x) = \int_0^{\tilde{\mu}} f(x) = 0.5 \]

variance:
\[ \sigma^2 = \int_{-\infty}^{\infty} (x =\mu_x)\cdot f(x) \]
Normal
\[ k = \frac{\mu + k \sigma - \mu}{\sigma} \]
standardize:
\[ \frac{x - \mu}{\sigma} \]
\[ -k = \frac{\mu - k \sigma - \mu}{\sigma} \]
upper quartile:
\[ \mu + 0.675\sigma \]
lower quartile:
\[ \mu - 0.675\sigma \]
Exponential
\[ -ln(c) \cdot \frac{1}{\lambda} \text{ where c is the quartile }(0.25,0.5,0.75) \]
\[ S_{xx} = \sum x_i^2 - \frac{1}{n}\left(\sum x_i\right)^2 = \sum(x_i - \bar{x})^2 \]
\[ S_{yy} = \sum y_i^2 - \frac{1}{n}\left(\sum y_i\right)^2 = \sum(y_i - \bar{y})^2 \]
\[ S_{xy} = \sum{x_i y_i} - \frac{1}{n}\left(\sum x_i\right)\left(\sum y_i\right) \] \[ \text{SSResid} = \text{SSE (error sum of squares)} = \sum(y_i - \hat{y}_i)^2 = S_{yy} - b S_{xy} \]
\[ \text{SSTo} = \text{SST} = S_{yy} = \text{Total sum of squares} = \text{SSRegr} + \text{SSE} = \text{SSTr} + \text{SSE} = \sum_i^k \sum_j^n (x_{ij} - \bar{\bar{x}})^2 \]
\[ \text{SSRegr} = \text{regression sum of squares} \]
\[ r^2 = 1 - \frac{\text{SSE}}{\text{SST}} = \frac{\text{SSRegr}}{\text{SST}} = \text{coefficient of determination} \]

\[ r = \frac{S_{xy}}{\sqrt{S_{xx}}\sqrt{S_{yy}}} \]
\[ \hat{\beta} = \frac{S_{xy}}{S_{xx}} \]
\[ \hat{\alpha} = \bar{y} - \beta\bar{x} \]
prediction:
\[ \hat{\alpha} = \bar{y} - \beta\bar{x} \]
Percentile ($$\eta_p$$):
\[ \int_{-\infty}^{\eta_p} f(x) = p \]

MSE (Mean Square Error) =
\[ \frac{1}{n} SSE = \frac{1}{n}\sum (y_i-\hat{y}_i)^2 = \frac{1}{n} \sum (y_i - \alpha - \beta x_i)^2 \]

MSTr (Mean Square for treatments)

ANOVA
\[ SST = SS_{\text{explained}} + SSE \]
\[ R^2 = 1 - \frac{SSE}{SST} \]
\[ \sum(y_i - \bar{y})^2 = \sum(\hat{y}_i - \bar{y})^2 + \sum(y_i - \hat{y}_i)^2 \]
\[ s_e^2 = \frac{SSE}{n-2} \text{ or } \frac{SSE}{n-(k+1)} \]
\[ R_{adj}^2 = 1-\frac{SSE(n-1)}{SST(n-(k+1))}\]
\[ H_0: \mu_1 = \mu_2 = .. = \mu_k \]
\[ \bar{\bar{x}} = \left(\frac{n_1}{n}\right)\bar{x}_1 + \left(\frac{n_2}{n}\right)\bar{x}_2 + ... + \left(\frac{n_k}{n}\right)\bar{x}_k \]
\[ SSTr = n_1(\bar{x}_1 - \bar{\bar{x}})^2 + n_2(\bar{x}_2 - \bar{\bar{x}})^2 + ... + n_k(\bar{x}_k - \bar{\bar{x}})^2 \]

SourcesdfSSMSF
Between Samples$$k-1$$SSTrMSTr$$\frac{\text{MSTr}}{\text{MSE}}$$
Within Samples$$n-k$$SSEMSE
Total$$n-1$$SST

One-sample t interval:
\[ \bar{x} \pm t^* \frac{s}{\sqrt{n}} \]
(CI)
Prediction interval:
\[ \bar{x} \pm t^* s\sqrt{1+\frac{1}{n}} \]
(PI)
Tolerance interval:
\[ \bar{x} \pm k^* s \]

Difference t interval:
\[ \bar{x}_1 - \bar{x}_2 \pm t^*\sqrt{\frac{s_1^2}{n_1} + \frac{s_2^2}{n_2}} \]

Adjusted
\[ R^2 = 1 - \left(\frac{n-1}{n-(k+1)}\right) \frac{SSE}{SST} \]

Type I error: Reject $$H_0$$ when true; If the F-test p-value is small, it's useful.
Type II error: Don't reject $$H_0$$ when false.
B(Type II) =
\[ z^* \sqrt{\frac{\sigma_1^2}{n_1} + \frac{\sigma_2^2}{n_2}} \]


Simple linear regression: $$y = \alpha + \beta x$$
General multiple regression: $$y = \alpha + \beta_1 x_1 + ... + \beta_k x_k$$
Prediction error: $$\hat{y} - y^* = \sqrt{s_{\hat{y}}^2 + s_e^2} \cdot t$$
\[ t = \frac{\hat{y}-y^*}{\sqrt{s_{\hat{y}}^2 + s_e^2}} \]

\[ P(\hat{y} - y^* > 11) = P\left(\sqrt{s_{\hat{y}}^2 + s_e^2} \cdot t > 11\right) = P\left(t > \frac{11}{\sqrt{s_{\hat{y}}^2 + s_e^2}}\right) \]

\[ \mu_{\hat{x}_1 - \hat{x}_2} = \mu_{\hat{x}_1} - \mu_{\hat{x}_2} = \mu_1 - \mu_2 \]
\[ \sigma_{\hat{x}_1 - \hat{x}_2} = \sqrt{\frac{\sigma_1^2}{n_1} + \frac{\sigma_2^2}{n_2}} \]
\[ \hat{x}_1 - \hat{x}_2 \pm z^* \sqrt{\frac{s_1^2}{n_1} + \frac{s_2^2}{n_2}} \]


To test if $$\mu_1 = \mu_2$$, use a two-sample t test with $$\delta = 0$$
If you're looking for the true average, it's a CI, not the standard deviation about the regression.
A large n value may indicate a z--test, but you must think about whether or not its paired or not paired.
A hypothesis is only valid if it tests a population parameter. Do not extrapolate outside of a regression analysis unless you use a future predictor.

F-Test
\[ F = \frac{MSRegr}{MSE} \]
\[ MSRegr = \frac{SSRegr}{k} \]
\[ MSResid = \frac{SSE}{n - (k+1)} \]
\[ H_0: \beta_1=\beta_2=...=\beta_k=0 \]


Chi-Squared ($$\chi^2$$)
\[ H_0: \pi_1 = \frac{\hat{n}_1}{n_1},\pi_2 = \frac{\hat{n}_2}{n_2}, ..., \pi_k = \frac{\hat{n}_k}{n_k} \]
\[ \chi^2 = \sum_{i=1}^k \frac{(n_i - \hat{n}_i)^2}{\hat{n}_i} = \sum \left(\frac{\text{observed - expected}}{\text{expected}}\right) \]


Linear Association Test
\[ H_0: p=0 \]
\[ t = \frac{r\sqrt{n-2}}{\sqrt{1-r^2}} \]
\[ \sigma_{\hat{y}} = \sigma \sqrt{\frac{1}{n} + \frac{(x^* - \bar{x})^2}{S_{xx}} } \]
\[ \mu_{\hat{y}} = \hat{y} = \alpha + \beta x^* \]
\[ \hat{y} \pm t^* s_{\hat{y}} df = n-2 \text{ for a mean y value (population)} \]
\[ \hat{y} \pm t^* \sqrt{s_e^2 + s_{\hat{y}}^2} df=n-2 \text{ for single future y-values (PI)} \]


Paired T-test
\[ \bar{d} = \bar{(x-y)} \]
\[ t = \frac{\bar{d} - \delta}{\frac{s_d}{\sqrt{n}}} \]
\[ \sigma_d = \sigma \text{ of x-y pairs } = s_d \]


Large Sample:
\[ z = \frac{\bar{x} - 0.5}{\frac{s}{\sqrt{n}}} \]
\[ \text{P-value } \le \alpha \]

Small Sample:
\[ z = \frac{\bar{x} - \mu}{\frac{s}{\sqrt{n}}} \]
\[ df = n-1 \]


Difference:
\[ H-0: \mu_1 - \mu_2 = \delta \]
\[ t = \frac{\bar{x}_1 - \bar{x}_2 - \delta}{\sqrt{\frac{s_1^2}{n_1} + \frac{s_2^2}{n_2}}} \]
\[ df = \frac{\left(\frac{s_1^2}{n_1} + \frac{s_2^2}{n_2} \right)}{\frac{1}{n_1-1} \left(\frac{s_1^2}{n_1}\right)^2 + \frac{1}{n_2-1} \left(\frac{s_2^2}{n_2}\right)^2 } \]