MPCS 50103 Mathematics for Computer Science: Discrete Mathematics (Autumn 2018)

Section 1
Instructor(s) Brady, Geraldine (gb52)
Location Kersten 105
Meeting Times Tuesday 2pm - 3:20pm
Thursday 2pm - 3:20pm
Website: http://people.cs.uchicago.edu/~brady/MPCS50103/
Fulfills Immersion Math

Syllabus

Course Description

This course is an introduction to ideas and techniques from discrete mathematics that are widely used in computer science.  The course emphasizes mathematical proof and problem solving, employed on a variety of useful topics in counting, discrete probability, graphs, and basic number theory. 

On completion of the course, students will have been trained to think about and use mathematical concepts and techniques to solve problems, and to express mathematical notions precisely. They will be able to use ideas and techniques from discrete mathematics in subsequent courses in computer science, in particular courses in algorithms, networks, numerical methods, software engineering, data analysis, and data mining.

Course Contents

Topics covered include: methods of proof; mathematical induction; basic counting (permutations, combinations, binomial theorem, pigeonhole principle, inclusion/exclusion); basic discrete probability (conditional probability, independence, Bernoulli trials, Bayes's theorem, random variables, expected value, variance, geometric and binomial distributions); basic graph theory; asymptotic notation and growth of functions; recurrences; and basic number theory.

 

Requirements

    Lectures: Students are responsible for all material presented in lectures. 

    Problem sessions: Weekly problem-solving sessions are held on Saturdays. Students are responsible for all material covered at the problem sessions. Class participation is encouraged.

    Homework: Weekly homework assignments are assigned after class and are due the following week.  Students are required to submit homework electronically and use LaTeX to prepare homework files.

    Exams: There are four quizzes (weeks 3, 4, 9, and 10), a midterm exam (week 5), and a final exam (week 11).  There will be no make-up exams.

 

Course grade

The course grade is based on homework, quizzes, and exams.

    Homework: 5%.

    Quizzes: 20% (5% for each of 4 quizzes).

    Midterm examination: 25%.

    Final examination: 50%.

 

Textbook

Discrete Mathematics and its Applications (7th edition) (McGraw-Hill) by Kenneth H. Rosen (ISBN 978-0073383095).

 

Prerequisites

Precalculus, especially logarithms and exponentials, is a prerequisite; calculus is recommended.  High-school level familiarity with sets, functions, and relations will be assumed.

 

There are no programming prerequisites.

Course Prerequisites

Other Prerequisites

Only MPCS students can register for this course.

Overlapping Classes

This class is scheduled at a time that does not conflict with any other classes this quarter.