Fall 2008
Topics |
Date(s) |
Reading |
Introduction and Overview : Significance of Formal Reasoning in All Aspects of Computer Science Examples of Cases that will be Discussed Lecture Outline (I) |
Tue, Aug 19 |
-----
|
Thu, Aug 21 |
Reading: Rosen pp 1-30. Theory emphasis: pp 1-6,10-11, Example 19 in pp 14, pp 22-25, Exercises 42-45 in pp 29. Application emphasis: pp 12-13, exercises 47-54 in pp 20. |
|
Predicates and Quantifiers Lecture Outline (III) Tue, Aug 26
Reading: Rosen, Pages 30-62. Theory emphasis: pp 31-32, pp 34-36, pp 40, Table 2 pp 41, pp 51-52, Table 1 pp 53. Application Emphasis: Example 25 pp 43-44, Logic Programming pp 45-46. | ||
Introducion to Proofs Rules of Logical Inference Lecture Outline (IV and V) Thu, Aug 28
Reading: Rosen, Pages 63-84. Emphasis: Introduction pp 63, Table 1 pp 66, pp 70-71, pp 75-84, | ||
Introducion to Proofs Direct proofs Indirect Proofs: Contradiction, Contraposition Lecture Outline (IV and V) Tue, Sept 2
Reading: Rosen, Pages 63-84. Emphasis: Introduction pp 63, Table 1 pp 66, pp 70-71, pp 75-84, | ||
Go over Homework 1 Proof Strategies Lecture Outline (VI and VII) Thu, Sept 4
Reading: Rosen, Pages 86-102. Emphasis: Examples 1, 2, 3, 6, 7, 8, 9, 14, 15, 16, 17 of Section 1.7, Tilings on Pages 97-100. | ||
Proof Strategies (continued) Direct Proofs, Contradiction, Contraposition, Existential Proofs Theorems, Lemmas, Claims, Facts, Corollaries Conjectures and Godel's Incompleteness Theorem (informal discussion) Lecture Outline (VI and VII) Tue, Sept 9
Reading: Rosen, Pages 86-102. Emphasis: Examples 1, 2, 3, 6, 7, 8, 9, 14, 15, 16, 17 of Section 1.7, Tilings on Pages 97-100. | ||
Two fundamental sums (in computer science and in general): 1+2 +3 + ... + n 1 + x + x^2 + x^3 + ... + x^n Direct proofs for the above sums and further demostration of Proof Strategies Lecture Outline: 1 2 Thu, Sept 11
Reading: Rosen, Pages 149-158. Emphasis: pp 150-151, pp 153: Summation Notation, pp 156 Example 13: Double Summation, pp 157 Table 2: Lines 1 and 2 | ||
How to study for Quiz 1: From Rosen Book: Logic: Tables 1,3,4 pp 22-23 Intro Proofs (direct, contrapositive, contradiction): pp 75-78 everything, pp 80-81 everything after Proofs by Contradiction pp 89, example 6 From Outline Lecture Notes: Lecture Outline (II), pp 1-11 Lecture Outline (III), everything Lecture Outline (IV) and (V), everything Lecture Outline (VI) and (VII), everything Homework 1 Probelms 5,6,7,8,10. Homework 2 Problems 1,3,4,5,6. Practice Quiz 1 , everything. Thu, Sept 18
Reading: See Left
| ||
Recursion: a fundamental conceptual primitive
Recursive Definitions and Recursive Algorithms I The previously studied sums 1+2+...+n and 1+x+...+x^n viewed recursively: S(n)=S(n-1)+n with S(1)=1 and X(n)=X(n-1)+x^n with X(0)=1 Binary Search T(n)=T(n/2)+1, with T(1)=1, heuristic intuitive solution T(n)=log_2(n)+1 Towers of Hanoi T(n)=2T(n-1)+1, with T(1)=1, heuristic intuitive solution T(n)=2^n+1 Thu, Sept 25
Reading: Rosen, Pages 294-296. | ||
Recursive Definitions and Recursive Algorithms II
Tiling, Fast Exponantiation Tue, Sept 30
Reading: Rosen, Page 277 example 13. pp 311-314, Algorithms 1,2,3,5 and 6. | ||
Induction as a Proof Technique (II)
Strategy: USE THE INDUCTIVE HYPOTHESIS TO CARRY THE PROOF OF THE INDUCTIVE STEP Inductive proofs concerning numbers and sums (eg 5 divides n^5-n, SUM_1^n(k^2^k)=(n+1)2^{n+1}+2) Inductive proofs concerning reccurences eg T(n)=T(n/2)+n, T(1)=1, solves to T(n)=2n(1-1/n) Tue, Oct 7
Reading: Rosen, Pages 273, examples 8,9. Rosen, Page 280, problems 33,34,14. | ||
Induction as a Proof Technique (III)
Strategy: USE THE INDUCTIVE HYPOTHESIS TO CARRY THE PROOF OF THE INDUCTIVE STEP Inductive proofs on Structures and Algorithms (meaning "things" other than numbers) Inductive proofs concerning reccurences revisited Mergesort: T(n)=2T(n/2)+n, T(1)=0, solves to T(n)=n log_n(n) Thu, Oct 9
Reading: Rosen, Pages 299-303 (Recursively Defined Structures) Rosen, Pages 303-307 (Structural Induction) Rosen, Pages 317-321 (Mergesort and its Analysis) | ||
Strong Induction (IV)
Thu, Oct 16
Reading: Rosen, Pages 283-288. | ||
Growth of Functions
(also extensive review of HW4) Tue, Oct 21
Reading: Rosen, Pages 180-188. | ||
Average and implications, Markov's Inequality Variance and implications, Chebychev's Inequality Lecture Outline Thu, Nov 6
| | |
How to make intelligent concusions about large datasets,
given small amount of information Markov and Chebychev's Inequalities revisited Tue, Nov 11
| | |
When Contrapositive and Contradition are essentially the same proof and how to not complicate your proofs unecessarily Thu, Nov 13 Reading: ---- | ||
Probability Primitives:
(exemplifying probability spaces) The Monty Hall Problem Expected Win of Simple Games Probability in Computer Science: Overview of Quicksort Discussion of Randomization in Computationally Hard Problems Tue, Nov 18 Reading: Rosen pages 393, 394, 398, 400-402, 408-410. | ||
On the relevance of theory and quantitative analysis Examples: (1) An argument on the power of recursion from Science Magazine (2) Some fun puzzles from Martin Gardener's book Make-up Quiz 2 Thu, Nov 20 Reading: ---- | ||
Uniform Distribution Binomial Distribution, Power-Law Distributions and their applications Tue, Nov 25 Reading: ---- | ||
Happy Thanksgiving ! Study Guide for Quiz 3 in the Announcement Section (dated Nov 24) Thu, Nov 27 | ||
Quiz 3
Tue, Dec 2
| | |
The final exam is Friday Dec 12, 11:30-2:20,
in the same classroom.
In the final, you are allowed 3 single-sided pages with notes. Any notes you want is fine. Study Guide for Final (in the order that follows): Quiz 3, Quiz 2, Practice Quiz 2, HW 6,5,4. Quiz 1, Practice Quiz 1, Hw 3,2,1. Thu, Dec 4 Study Guide for Final (in the order that follows): Quiz 3, Quiz 2, Practice Quiz 2, HW 6,5,4. Quiz 1, Practice Quiz 1, Hw 3,2,1. |
