Lecture 5: Diagonalization, functions and sums review
8984 views
|
1
rating
Lesson Description:
Learn about diagonalization, functions, and a review of sums.
More information about this course:
http://www.aduni.org/courses/discrete
Licensed under Creative Commons Attribution ShareAlike 2.0:
http://creativecommons.org/licenses/by-sa/2.0/
Additional Resources:
- Lecture Notes - Lecture Notes from the course
- Problem Set 2 - A problem set with some problems from this lecture
- Problem Set 2 Solutions - Solutions to the Problem Set
Questions answered by this video:
- What is a conundrome in Discrete Math?
- What is Russell's Paradox or the Barber's Paradox?
- If there is a town in which everyone either shaves himself or goes to the barber, does the barber shave himself?
- Why is there no program that finds infinite loops in other programs?
- What is a function, and what does it mean for a function to have one-to-one correspondence?
- What is domain and range for a function?
- What does it mean for a function to be onto?
- Which is larger, x^(log x) or (log x)^x?
- What is the proof that 1^3 + 2^3 + 3^3 + ... + n^3 = (1 + 2 + 3 + ... + n)^2 using induction?
- How can you find and prove the sum of 1^2 + 2^2 + 3^2 + ... + n^2 without induction?
- How do you write and use sigma notation for sums?
- How do you find the sum of squares by finding the sum of consecutive odd integers and manipulating the sum?
- What is the sum of (n - i + 1)(2i - 1) from i = 1 to n?
-
Staff Review
This video starts out with an intriguing barber paradox, and uses this as an analogy to a computer program, and then outlines a proof by contradiction to say that such a program cannot exist. Then, functions are discussed in some detail. Next, some more about complexity with Big O and Big Theta are reviewed. Some really interesting and complex sums of series are calculated.
