Office: 337 Illini Hall,
Email: jmmackay at illinois dot edu
Question: Can you find a way, starting from a place of your choosing, to cross all the bridges in the city of Königsberg? You are only allowed to cross each bridge once.
This question, and its solution, is best understood by introducing a discrete structure (called a graph). As we will see, problems with a discrete structure are particularly common in computer science and related fields. In this course we will cover the basics of discrete mathematics.
We will study objects such as sets, functions, relations, graphs and trees, and you will learn techniques of counting (harder than you might think) and probability. Along the way, we'll see the basic methods of proof used in mathematics and logic. Finally, in all these areas, we will emphasise ways -- algorithms -- to actually work out problems, and study how efficient these algorithms are.
There will be weekly homework assignments, collected at the start of class on Fridays. The first homework assignment will be due the end of the second week of class.
You are free (and encouraged) to work with fellow students on the homework problems. However, you should write up your final solutions by yourself. If your solutions to an assignment resulted from discussions with your fellow students, you should list their names at the end of your assignment. (It is good to get in the habit of giving credit where credit is due.)
Your lowest homework score will be dropped.
Most weeks there will be a short (~10 minute) quiz at the start of class on Friday.
There will be three hour long exams in class, and a final. The class exams are set to be on October 1, November 5 and December 3.
The first class exam will cover material through section 5.2. The second class exam will cover material from 5.3 through to the end of Chapter 7. The third class exam will cover material from Chapters 8, 9 and 10.
(Note that this is provisional and may be adjusted as the semester progresses.)
The final will be on Friday, December 12 from 7:00-10:00 PM, and will cover all the material we have seen on the course.
Your grade will be determined as follows:
25% homework, 12.5% quiz, 3 * 12.5% hour exams, 25% final.
Letter grades will be assigned according to: A+- 85%, B+- 70%, C+- 55%, D+- 40%, F for less than 40%. This may be adjusted downwards if necessary.
I reserve the right to give a lower grade in exceptional circumstances, such as failing to complete multiple homework assignments, or missing exams without reason. Cheating may result in a substantially lower grade, or even an F.
If you are ill or otherwise unable to complete an assignment on time, or take an exam, please get a letter from the dean's office (http://www.odos.uiuc.edu/).
To insure that disability-related concerns are properly addressed from the beginning, students with disabilities who require assistance to participate in this class, or alternative exam arrangements, are asked to contact me as soon as possible.
— Return Home —