Math/CS 240: Introduction to Discrete Mathematics

TA: Harris Nover

JE's Office Hours:

Tuesdays, 12:30-1:30pm, Chadbourne Residential College dining hall

HN's Office Hours:

Mondays and Wednesdays, 12-1, VV 822

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.

Please notice that Professor Joseph and I will be teaching the two sections of Math/CS 240 from different textbooks. The two sections are always taught separately, with separate homework and exams, but this semester they will diverge a bit more than usual as we decide which text to use in the future. So please be aware that the two lectures are not interchangeable.

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 11 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 18 Sep:	1.6: 8,12,17a,30; 1.7: 3,22,28,41,42; 2.1: 4,16,34,36, 2.2: 4,14,16,48;
due 25 Sep:	2.3: 4,8cdg,12,13,15be,18,25,32,60,65; 2.4: 3,15ad,18,23,25;
due 2 Oct:	3.1: 4,11,16,52,56; 3.2: 2,5,9,15,20ab,24,48; 3.3:4,5,10,27; + traveling salesman problem (e-mailed to you)
due 9 Oct:	3.4 7,10c,16,21,23,24,31c,32c; 3.5: 5,6; 3.6:2a,3a,5
due 16 Oct:	3.5:10,12,17,18,28a; 3.6: 19,20,24bcd; 3.7: 6,7,12,18
due 23 Oct:	3.7: 27,46,47,48,52
due 30 Oct:	4.1: 3,4,8,9,10,18,20,22,32,47,50; 4.2: 3,7,11; 4.3: 2,5; extra tic tac toe problem (e-mailed to you)
due 6 Nov:	4.3 13,44; 4.4 4,13,24,35,37; three extra problems e-mailed to you.
due 13 Nov:	5.1 3,7,15,24ab,26,52,53; 5.3: 3,5ac,11d; 5.4: 6,7; 5.5: 17
due 26 Nov (note date!):	5.3: 9,16,22ac; 6.1:5,6,8,9,16,28,31; 6.2:9,16,23,26,31,38; 6.3: 10,16,18,21
due: 4 Dec	6.4: 3,6,7,10,12,16,23; extra probability problems (e-mailed to you)
due: 11 Dec	6.4:14,15,24,25,38,39,41;7.1: 4,5,19,24; 7.2: 3abc,4abc,8,11; extra variance problems (e-mailed to you)

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.