Syllabus Collection >
Please use this identifier to cite or link to this item:
|Title: ||Introduction to Computation|
|Issue Date: |
|Abstract: ||CMPSCI 250
Introduction to Computation
(Last Modified September 25, 2005. Subject to additional changes)
Lecture Date Class Topic Reading (before class) Details Homework Assigned Homework Due
Lecture 1 Th Sept 8 Introduction and course overview; Propositional Logic 1.1, 1.2 Everything in these sections. Ex. Set 1
Lecture 2 Tu Sept 13 Predicates and Quantifiers 1.3, 1.4 Everything in these sections.
Lecture 3 Th Sept 15 Proof Methods 1.5 Everything except you don't need to memorize Tables 1 and 2. However, know how to use these rules and know the name Modus Ponens. Ex. Set 2
Lecture 4 Tu Sept 20 Sets and Functions 1.6, 1.7 Everything in these sections.
Sept 20: Last day to drop with no record
Lecture 5 Th Sept 22 More Functions and Relations 1.8, 7.1 Ex. Set 1
Lecture 6 Tu Sept 27 Equivalence Relations and Partial Orderings 7.5, 7.6 up to but not including Lattices Example 4 on p. 509 is something we will get to later.
Lecture 7 Th Sept 29 Divisibility and Primes 2.4, 2.5, skip pp. 172-175 up to Modular Exponentiation This and the next lecture touch on number theory. It is hard going, but we'll end up with understanding public key cryptography. Hang in there. With luck, I will explain all! Ex. Set 3 Ex. Set 2
Lecture 8 Tu Oct 4 Applications of Number Theory 2.6 Everything in this section.
Lecture 9 Th Oct 6 More applications of Number Theory: Cryptosystems I presented some material not in the book on breaking affine cyphers
Oct 6: Evening Midterm. This will cover everything from Lecture 1 up to and including Lecture 6. Closed book. 6:00-7:30 pm ECSC0119
Lecture 10 Tu Oct 11 Public Key Cryptography: RSA Note: we are skipping most of the in-class discussion of Proof Strategies from Sec. 3.1 but you should still read this section.
Lecture 11 Th Oct 13 Sequences and Summations 3.2 This is an easy section that should be review for most of you, but we'll end up with the key concept of cardinality. (We will first finish discussing the RSA cryptosystem.) Ex. Set 4 Ex. Set 3
Lecture 12 Tu Oct 18 Mathematical Induction 3.3 Everything in this section.
Lecture 13 Th Oct 20 Recursive Definitions and Structural Induction 3.4 Everything in this section.
Lecture 14 Tu Oct 25 Recursive Algorithms and Program Correctness 3.5, 3.6 Everything in these sections.
Lecture 15 Th Oct 27 Combinatorics: Sum and Product Rules; Pigeonhole Principle 4.1, 4.2 Everything in these section. Ex. Set 5 Ex. Set 4
Oct 31: Mid Semester; Last day to drop with W
Lecture 16 Tu Nov 1 Permutations and Combinations 4.3, 4.4 Everything in these sections. You need to memorize the binomial theorem but not the corollaries. But you should know how to generate them.
Lecture 17 Th Nov 3 Generalized Permutations and Combinations 4.5 Just when you thought you knew how to count! Ex. Set 6 Ex. Set 5
Lecture 18 Tu Nov 8 Probability Theory 5.1, 5.2 up to but not including Monte Carlo Algorithms Think about the Monte Hall Puzzle on p. 360, but try not to look at the solution. We'll have fun with this.
Lecture 19 Th Nov 10 Expected Value and Variance 5.3 Everything in this section.
Nov 10: Evening Midterm. This will cover everything from Lecture 7 up to and including Lecture 17, i.e., basically number theory, induction and combinatorics. Closed book. 6:00-7:30 pm ECSC 119
Lecture 20 Tu Nov 15 Graphs 8.1, 8.2 Everything in these sections.
Lecture 21 Th Nov 17 More Graphs 8.4 up through p. 573, 8.5, 8.8 Everything in these sections. Ex. Set 7
Lecture 22 Tu Nov 22 Trees 9.1, 9.2 up to but not including prefix codes You will see a lot more about trees in CMPSCI 383. Ex. Set 7 Ex. Set 6
Lecture 23 Tu Nov 29 Formal Languages 11.1 Everything in this section.
Lecture 24 Th Dec 1 Finite State Machines 11.2, 11.3 Everything in these sections. Ex. Set 8
Lecture 25 Tu Dec 6 Regular Sets and Kleene's Theorem 11.4 Everything in this section. Ex. Set 7
Lecture 26 Th Dec 8 Turing Machines 11.5 Everything in this section.
Lecture 27 Tu Dec 13 Review and Discussion Bring your questions about anything covered from the beginning of the course. Ex. Set 8
Final Exam. Two-hour closed-book during exam period. Monday 19 December 2005, 10:30 am, AEBN0119|
|Appears in Collections:||Syllabus|
Files in This Item:
All items in DSpace are protected by copyright, with all rights reserved.