0
0

Sign in to rate
# Mathematics for Computer Science: MIT OCW 6.042

0.17MB. 0 audio & 1 images. Updated 2016-08-24.

## Description

## Sample (from 528 notes)

**Cards are customizable!**When this deck is imported into the desktop program, cards will appear as the deck author has made them. If you'd like to customize what appears on the front and back of a card, you can do so by clicking the Edit button, and then clicking the Cards button.

Term |
Euler Tour |

Definition |
An \textit {Euler tour} is a defined to be a walk that traverses every edge in a graph exactly once and which starts and finishes at the same vertex. |

Subject |
DISCRETE MATH |

Tags |
chapter_5 euler_tour graph_theory paths walks |

Question |
What is the recurrence equation for the number of ways there are to climb $n$ stairs if you can either step up one stair or hop of two? |

Answer |
There is only 1 way to way to climb 0 stairs: do nothing. There is only 1 way to climb 1 stair: step up. In general, an ascent of $n$ stairs consists of either a step followed by an ascent of the remaining $n - 1$ stairs or a hop followed by an ascent of $n - 2$ stairs. So the total number of ways to climb $n$ stairs is equal to the number of ways to climb $n - 1$ plus the number of ways to climb $n - 2$. These observations define a recurrence:\begin{align*}f(0) &= 1 \qquad & \\f(1) &= 1 \qquad & \\f(n) &= f(n - 1) + f(n - 2) \qquad & \text{(for }n \geq 2)\end{align*}$f(n)$ denotes the number of ways to climb $n$ stairs. |

Subject |
DISCRETE MATH |

Tags |
chapter_12 fibonacci_series recurrences recursion series sums |

Term |
Neighbors |

Definition |
In any graph, the set $N(S)$ of \textit{neighbors} of some set $S$ of vertices is the set of all vertices adjacent to some vertex in $S$. That is: \[ N(S) ::= \{ r\, |\, \{s, r\} {\text { is a edge for some }} s \in S \} \] |

Subject |
DISCRETE MATH |

Tags |
chapter_5 graph_theory |

After the file is downloaded, double-click on it to open it in the desktop program.

At this time, it is not possible to add shared decks directly to your AnkiWeb account - they need to be added from the desktop then synchronized to AnkiWeb.