### Algorithms

[component=861]

We start with the fundamentals including asymptotic notations, basic efficiency classes, mathematical analysis of recursive and non-recursive algorithms. We then study divide-and-conquer techniques (quick-sort, binary search, matrix multiplication, convex-hull problems), decrease-and-conquer (depth/breadth first search, topological sort), transform-and-conquer (Gaussian elimination, balanced trees, heaps), dynamic programming (Binomial coefficients, Warshall's and Floyd's algorithm, knapsack problem, optimal matrix multiplication order), string matching, hashing, greedy techniques (Prim's algorithm, Kruskal's algorithm, Dijkstra's Algorithm, Huffman trees). The last two weeks of the semester is an introduction of basic computability (tractability, P/NP/NP-complete classes).

**2010 Quotes; thanks Blake!**

- Ali: What is an expected value? Allison?
- Allison: It is a value... that is... expected?!?
- Ali: Oh my... You used to be good.

---

- Ali: [Breaks the class into groups of three or four people] OK, I want each group to discuss the problem and propose a solution. [After a minute of complete silence] I hear nothing. You should be talking now.
- Alex/Paul/Griffin/Blake: [Mumbling some stuff about something completely unrelated to data structures]
- Ali: Hey, what are you people talking about?
- Alex: Lindsay Lohan.
- Ali: You're supposed to be talking about THE PROBLEM!
- Paul: Lindsey Lohan is a problem.

---

- Ali: [Trying to better explain the summation variable in the internal path length for binary trees] The i variable determines the sizes of the two trees being merged into one. It does not have to be equal to half the number of nodes. For example, [drawing an imaginary line down the middle of the classroom] if I draw a line like this, I can split my students into those that I like and those that I don't.
- Someone at the back: Which side is which?
- Ali: That's not important now. But, just like the i variable could be small, I can draw the line differently [draws the line around Juan]
- Blake: So Juan is the student you like right?
- Ali: [Sarcastically] Yeah that's what I must have meant.
- Juan: It's OK, I have other professors.

---

- Ali: Therefore, when you instantiate an inner class, the resulting object is implicitly connected with an instance of the outer object. Just like that line on the board illustrates.
- Evan: It's like one of them has a leash on the other.
- Ali: Yes, but please don't take that analogy any further.
- Jared: In my mind, I already did.
- Ali: Why am I not surprised?

---

- Ali: [Talking about some asymptotic complexity stuff]
- Juan: [All excited] We are doing this same thing in physical chemistry!
- Ali: [Insincerely] Well isn't that nice...

---

- Allison: [After 6 months of sitting on the same seat, decides to move the other side of the classroom]
- Someone in the background: She is one of us now. Welcome to the dark side!
- Matt: The force is strong with this one.
- Someone else in the background: She does look like a Jedi knight.
- Ali: You're more messed up than I am!

---

- Ali: So it is, after all, NlgN complexity. Juan, do you agree?
- Juan: No, I concur.
- Ali: Man, what's wrong with you? It's like this every semester.

---

- Ali: Does this look balanced to you?
- Evan: Yes!
- Ali: The answer was no.
- Evan: [Shattered]
- Everyone: [Laughter]

---

- Blake: That's when we were talking about swapping the order of train cars.
- Ali: Oh yes, I remember that lab. That was when I was frantically putting together stuff before I left for Indiana.
- Blake: Well, I enjoyed not having class that week.
- Ali: Well, I enjoyed not going to class.

---

- Blake: Your slides said you pick the first child from the right subtree.
- Ali: No, that's not what my slides said.
- Blake: I am positive they did.
- Ali: Wanna bet?
- Blake: For what?
- Ali: $5000.
- Blake: I don't have $5000!
- Ali: OK, a candy bar.
- Corey: How do you go from $5000 to a candy bar?!?
- Blake: What's your favorite one?
- Ali: Milkyway!
- Blake: Mine too!
- Ali: Good, we can share it.

---

- Ali: [In order to "spice things up", has each person sit on the mirror side of where he/she sits]
- Class: [Moans, groans]
- Matt: Now that I have to look the other way, my neck is all messed up.

---

- Ali: If you look at the slides, the trees should look familiar.
- Matt: [Looking at the Splay Trees slides] I knew this tree looked familiar! Its Treebeard!!!

---

- Ali: B-trees add levels as numbers are added and the tree fills up to capacity.
- Matt: Oh, that's kind of like what they are doing in Dubai!
- Ali: [Points at Blake] Are you writing these down!?

---

- Ali: Oh my... So I need to find a good application of calculus to convince you why it matters...
- Emily: What about physics?
- Ali: Physics? I am not a "physician"... I mean a "physicist".