Math/CS 240: Introduction to Discrete Mathematics

Professor: Jordan Ellenberg

TAs: Baris Aydinlioglu, Hao Lin

JE's Office Hours:

Tuesdays, 1:30-2:30pm, Van Vleck 323

HL's Office Hours:

TTh, 1-2, Van Vleck 101

BA's Office Hours:

MW, 10:30-11:30, Van Vleck 416

Course Syllabus (note: this is accurate as of the beginning of the term; JE will keep you apprised as exams approach of exactly what chapters will appear on each exam.)

Text:

Discrete Math and its Applications, K. Rosen, 6th edition.

Course Summary:

Mathematics can be loosely divided into two parts. The first is continuous mathematics; as the name suggests, this part of math treats phenomena that can be moved continuously, like functions, curves, and geometric spaces. Most of the math you've learned so far -- geometry, trigonometry, calculus -- is continuous in nature. The basic object of continuous mathematics is the real number line. Because the physical universe (at least to the naked eye) is continuous, this is the part of mathematics most associated with physics. The second part is discrete mathematics, the subject of our course. Here we throw aside any notion of continuous variation. The basic objects of discrete mathematics are the set of integers and of logical values; there is no way to move continuously from 2 to 3, or from "true" to "false." Because the states of a computer are discrete, this is the part of mathematics most associated with computer science.

Math/CS 240 covers the fundamentals of discrete mathematics. It is a requirement for the BS degree programs in Computer Engineering offered by the ECE Department and in Computer Science offered by the CS Department. It is now a prerequisite for (getting into) advanced computer science courses (CS 367, 520 and 577). The course is a foundational math course for this program and is meant to be taken early in the program; it is also a good foundation for higher mathematics courses. We will aim for breadth, not depth; you will be introduced to many new concepts and topics, and we won't spend a long time on any one of them. We hope that by the end of the course you'll have developed a friendly acquaintance with this important segment of mathematics, and have the expertise necessary to develop a deeper relationship with whatever topics you will need in your future studies.

The prerequisite for the course is Math 221 (Calculus I), and the course will be taught roughly on the level of Math 222 (Calculus II.) These prerequisites are meant to establish a base level of mathematical sophistication; we will not actually use calculus in the course.

Briefly, the topics covered in the course include: logic, set theory, functions and their orders of growth, the integers, algorithms, inductive and recursive definitions and arguments, program correctness, fundamentals of counting and discrete probability, trees and random walks, basic number theory including number-theoretic cryptography, variance and expected value, recurrence relations, . . . This is a long list, but you'll find that there are many connections between the topics.

Jump to:

Homework assignments

Important Announcements

Getting Help

Classlist

Go to:

Math Lab

GUTS

List of Private Math Tutors

ANNOUNCEMENTS:

HOMEWORK:

due 10 Sep:	1.1: 4bd,6f,10adf,28ade. 1.2:7b,8a,9e,14,19,22. 1.3:8abcd,10ab,14,16,44. 1.4: 6abcde, 10abcf,26aceg. 1.6:16,22.
due 17 Sep:	1.6: 6,8,12,16,18a,30; 1.7: 2,3,4,15,22,28,41,42; 2.1: 4,16,34,36
due 24 Sep:	2.2: 4,14,16,48; 2.3: 4,8cdg,12,13,15be,18,25,32,60,65; 2.4: 3,15ad,18,23,25;
due 1 Oct:	2.4: 32; 3.1: 4,11,16,25,52,56; 3.2: 2,5,9,15,20ab,24,48; 3.3:4,5;
due 8 Oct:	3.3:10,15,24,25,28; extra traveling salesman and halting problems e-mailed to you.
due 15 Oct:	3.4: 7,8,16ad,21,24,31c,32c,33; 3.5: 4abcd,7,11,17,22,24,31; syphilis problem (e-mailed to you)
due 22 Oct:	3.5: 18,26; 3.6: 2,3,5,20,21,30; 3.7: 4,6,7,18,27,46,47;
due 29 Oct:	4.1: 3,4,8,9,10,18,20,22,32,47,50; 4.2: 3,7,11; 4.3: 2,5; extra recursive function problem (e-mailed to you)
due 5 Nov:	4.2: 12,29,32; 4.3 13,26,27,44; 5.1: 3,7,15,24ab,26,52,53; Fibonacci, tic-tac-toe and tree problem e-mailed to you.
due 12 Nov:	4.4: 6,24,28,45; 5.5: 30; extra problems on trees and complexity of factorization, e-mailed to you
due 19 Nov:	5.3: 8,9,12,16,22ac;5.4: 6,7,28; 6.1:5,6,8,9,16,28,31; 6.2:9,16,23,26,31,38;
due: 3 Dec	6.2:9,16,23,26,31,38; 6.3: 10,16,18,21; 6.4: 3,6,7,10,12,16,23; possible extra probability problems (e-mailed to you).
due: 10 Dec

Getting Help

The first step should always be to see your TA or Prof. Ellenberg during office hours. You can also make use of the following resources:

Math Lab A free drop-in tutorial program in Van Vleck staffed by TAs and undergraduate tutors.
GUTS A free student-run program covering a variety of subjects. Staffed mostly by student volunteers.

Classlist
An email Classlist has been created for important announcements about this course. All students enrolled in the course are automatically added to the list. Your @wisc.edu or @students.wisc.edu email address is the one that will be used for the list, as well as for all other official communication from the University, so check your email frequently; if I send something to the list, I will assume everyone in the class has read it. If you are not enrolled in the course, but would like to be added to the list, please email Prof. Ellenberg.