CSCE 222 Discrete Structures for Computing
Spring 2011
Course Information
Instructor: Andreas Klappenecker
Where: HRBB 124
When: MWF 1:50-2:40pm.
Office: HRBB 509B
Course Information: Syllabus
Office hours:
Dr. Klappenecker @ Bright 509B,
TA Jung-Hwan Kim @ HRBB 214,
TA Wen Li @ Reed McDonald 229A,
TA Jianjie Zhang @ Richardson 912A,
PT Shena Hoffman @ Reed McDonald 111J,
PT Andy Hampton @ Reed McDonald 111J
- Monday: Hampton 9:30-11:00, Klappenecker 2:50-3:50, Hoffman 3:00-4:00
- Tuesday: Kim 11:00-1:00, Li: 1:30-3:30, Hoffman 2:20-3:35
- Wednesday: Li 10:30-12:30, Hoffman 3:00-4:00,
- Thursday: Zhang 1:00-5:00, Klappenecker 2:00-3:00, Hoffman 2:20-3:35,
Hampton 5:30-6:30
- Friday: Hampton 9:30-11:00, Kim 3:00-5:00,
- Office hours are subject to change.
This course discusses some basic mathematical techniques that are
useful in the analysis of algorithms. In particular, we will discuss
proof techniques; basic mathematical notions such as sets, functions,
and relations; basic techniques from combinatorics concerning counting
and recurrence relations. We will give a brief introduction to
algorithms and their complexity, and discuss the
automata and the Turing machine models of computation.
Announcements
Homework
Schedule
- W Jan 19 Syllabus, Asymptotic Notations
- F Jan 21 Asymptotic Notations
- M Jan 24 Time Complexity of Algorithms
pdf keynote
- W Jan 26 Propositional Logic, Quiz 1
- F Jan 28 Propositional Logic
pdf keynote
- M Jan 31 Propositional Logic, Ruby
pdf keynote
- W Feb 02 Predicate Logic, Quiz 2
- F Feb 04 No class due to weather
- M Feb 07 Predicate Logic
pdf keynote
- W Feb 09 Sets, Quiz 3
- F Feb 11 Sets and Functions
- M Feb 14 Functions, Sums
- W Feb 16 Sums
- F Feb 18 Review pdf keynote
- M Feb 21 Midterm 1
- W Feb 23 Midterm 1 solutions
- F Feb 25 Relations
- M Feb 28 Relations
- W Mar 02 Relations
- F Mar 04 Proof techniques
- M Mar 07 Proof techniques
- W Mar 09 Counting
pdf keynote ppt
- F Mar 11 Counting, Quiz
- M Mar 21 Review
- W Mar 23 Midterm Exam 2
- F Mar 25 Midterm Exam 2 Solutions
- M Mar 28 Counting
- W Mar 30 Solving Recurrence Relations
- F Apr 01 Solving Recurrence Relations
- M Apr 04 Generating Functions
- W Apr 06 Generating Functions, Master Theorem, Quiz
- F Apr 08 Master Theorem, Formal Languages
- M Apr 11 Formal Languages
- W Apr 13 Finite State Machines
- F Apr 15 Finite State Automata, Quiz
- M Apr 18 Turing Machines
- W Apr 20 Turing Machines, Undecidability
- F Apr 22 Reading Day
- M Apr 25 Undecidability, Quiz key ppt pdf
- W Apr 25 Extended Euclidean Algorithm pdf
- F Apr 27 RSA pdf
- M May 02 RSA (see Sections 3.6 and 3.7 for exercises about Euclid, CR, and other basics)
- T May 02 Review
Suggested Reading
