Discrete Mathematics

Homework | 10 @ 3.5% each | 35% |

Midterm | 25% | |

Final Exam | 40% | |

Total | 100% |

Friday, October 13.

- Analyze a proposition and determine its truth given information on the truth values of its components.
- Read various types of proofs and determine their validity.
- Construct valid proofs.
- Use sets to model fundamental problems in computer science.
- Use relations and functions to implement and study various computer operations.
- Use algorithm analysis to determine the space- and time-complexity of standard computer algorithms.
- Use combinatorics to analyse more complex algorithms.
- Use probability theory to analyse algorithms involving randomness.
- Use graph theory to model and solve various problems in computer science.

Week | Material |

8/22-8/25 | Preliminaries. What is discrete math. |

8/28-9/1 | Basic logic. |

Homework 1 due Fri, 9/1. | |

9/5-9/8 | Biconditionals, tautologies, contradictions. |

Homework 2 due Fri, 9/8. | |

9/11-9/15 | Sets. |

Homework 3 due Fri, 9/15. | |

9/18-9/22 | Quantifiers. |

Homework 4 due Fri, 9/22. | |

9/25-9/29 | Methods of proof. |

Homework 5 due Fri, 9/29. | |

10/2-10/6 | Counterexamples, existence. |

Homework 6 due Fri, 10/6. | |

10/9-10/13 | Mathematical induction. |

Midterm, Fri, 10/13. | |

10/18-10/20 | Sequences and series. |

Homework 7 due Fri, 10/20. | |

10/23-10/27 | Relations and equivalence relations. |

Homework 8 due Fri, 10/27. | |

10/30-11/3 | Functions, cardinality. |

Homework 9 due Fri, 11/3. | |

11/6-11/10 | Algorithms and complexity. |

Homework 10 due Fri, 11/10. | |

11/13-11/17 | More on algorithms and complexity |

Homework 11 due Fri, 11/17. | |

11/20-11/22 | Basic combinatorics. |

11/27-12/1 | Discrete probability. |

Homework 12 due Fri, 12/1. | |

12/4-12/6 | Graphs, shortest path and spanning trees. |

File translated from T

On 22 Aug 2017, 20:05.