| Class meeting |
11:00–11:50 MWF Austin 303 |
|---|---|
| Instructor | Karl Abrahamson |
| Office | Sci&Tech C-113 |
| Office hours | MWF 3:00–3:50 and Th 10:30–11:30 or by appointment |
| Phone | 328-9689 |
| abrahamsonk@ecu.edu | |
| Course web page | www.cs.ecu.edu/~karl/2405/spr20/ |
| My web page | www.cs.ecu.edu/~karl/ |
| Textbook | Discrete Mathematics and Its Applications, eighth edition. Kenneth H. Rosen. McGraw-Hill. |
The prerequisite is CSCI 2400, Discrete Mathematics I, or equivalent. You should be familiar with:
logic and proofs, including both propositional and first-order logic and including proof by contradiction;
sets, set notation and set operations;
functions and properties of functions;
sequences and sums of sequences;
relations, including partial orders and including properties of relations and operations on relations;
elementary number theory, including congruences.
The following is an approximate list of topics to be covered.
Review of proofs.
Peano Induction. Strong induction. (Rosen, chapters 5.1, 5.2, 5.3)
Graphs. Properties of graphs. Algorithms on graphs. (Rosen, chapters 10.1, 10.2, 10.3, 10.4, 10.7)
Trees. Properties of trees. Spanning trees. Algorithms on trees. (Rosen, chapters 11.1, 11.2)
Counting. Basic counting techniques. Permutations and combinations. The pigeonhole principle. Permutations and combinations. Inclusion-exclusion. (Rosen, chapters 6.1, 6.2, 6.3, 6.4, 6.5)
Linear recurrences. Recurrences for divide-and-conquer algorithms. Solving recurrences. (Rosen, chapters 8.1, 8.2, 8.3)
After successfully completing this course, students will have the following abilities.
Prove mathematical statements using Peano induction and strong induction.
Define directed and undirected graphs and trees. Define special types of graphs.
Understand representations schemes for graphs and be able to convert between them.
Demonstrate that graphs are or are not isomorphic.
Explain paths and connectivity in graphs. Be aware of path problems. Find connected components of a graph.
Apply Kuratowski's theorem and Euler's theorem to planar graphs and planar embeddings of graphs.
Explain properties of trees and kinds of trees. Explain depth-first search and depth-first-search trees.
Derive the size of large sets using basic counting theorems, including inclusion-exclusion and the pigeon-hole principle.
Apply theorems concerning permutations and combinations to counting problems.
Derive solutions to homogeneous and nonhomogeneous linear recurrences. Solve elementary divide-and-conquer recurrences.
There will be 5 midterm exams, on the following dates.
There will be no makeups for missed exams.
You can bring one prepared 8.5x11" piece of paper, written on both sides, to each exam. You can write anything that you like on that paper. I will not collect it.
The final exam will take place at 11:00–1:30 Friday, May 1. The final exam will cover all of the material for the course. You can bring two prepared 8.5x11" pieces of paper to the final exam.
There will be 5 homework assignments. All of the homework assignments and due dates are listed on the course web page.
Homework assignments do not count toward your grade. You will have at least 1 week to complete each assignment. I will mark your completed assignments and return them to you. I will go over common mistakes that students made in their submitted homework. An exam on the material of that homework assignment will take place after that.
Because the homework assignments are not given a grade and do not count directly toward your course grade, you are probably already thinking that there is no point in doing the homework. That would be incorrect.
The homework gives you an opportunity get experience solving problems that are similar to problems that will be on the exam. If you do not do the homework, then you will encounter problems on the exam without having solved any similar problems yourself. You will do poorly on the exam. Since your course grade is based on your performance on the exams, you will do poorly in this course. In fact, it is highly likely that you will fail this course.
Solutions to all of the assignment problems are available on the Internet. Suppose that you do a homework assignment by copying solutions that you get online. Finding and copying other people's solutions only gives you experience in finding and copying other people's solutions. See item 1.
By signing up for this class, you are committing yourself to attending class. Attendance is mandatory. Attendance will count toward your grade: you will lose points for unexcused absenses according to the following rules.
Attendence does not count during the first week of classes, since students might add during that time. After that, each unexecused absence counts the following number of points against your score, out of 100.
| n | Points lost for the n-th absence |
|---|---|
| 1 | 0 |
| 2 | 0 |
| 3 | 1 |
| 4 | 2 |
| 5 | 4 |
| 6 | 6 |
| 7 | 8 |
| 8 | 10 |
| 9 | 12 |
As you can see, you get two free unexecused absences. After that, the points increase. If you have 9 unexecused absences, you lose 0 + 0 + 1 + 2 + 4 + 6 + 8 + 10 + 12 = 43 points, and you cannot pass this course.
If you cannot accept this requirement, then you should drop this course.
Turn off your cell phone while in class. Any student found to be using a cell phone during class will be marked absent. If you cannot survive without your cell phone for 50 minutes, drop this course and seek counseling.
Grades will be computed as follows. Each midterm exam counts the same amount toward your grade. Percentages will be chosen from the given ranges to maximize your score.
| Grading | |
|---|---|
| 5 midterms | 60%–75% total |
| A comprehensive final exam | 25%–40% |
Note that attendance is not listed. It comes off the top of the grade that is computed based on exams.
Tentative cutoffs for grades will be as follows. These cutoffs will not be raised.
| Grade cutoffs | |||
|---|---|---|---|
| A | 93% | C+ | 76% |
| A– | 90% | C | 72% |
| B+ | 87% | C– | 68% |
| B | 83% | D+ | 64% |
| B– | 80% | D | 60% |
| D– | 56% | ||
No incompletes will be issued in this course except for extraordinary circumstances, and even then only if you are nearly done already and have done work of acceptable quality, so that it is realistic that you can pass the course. An incomplete will not be given simply because a student could not find the time to do the course work. By registering for this course, you are committing to finding time to do the work.
| 0. | 1/13–1/15 | Review of proof methods | |
| 1. | 1/17–1/29 | Mathematical induction (Chapter 5) | |
| 2. | 1/31–2/17 | Graphs (Chapter 10) | |
| 3. | 2/19–2/26 | Trees (Chapter 11) | |
| 4. | 3/2–3/27 | Counting (combinatorics) (Chapter 6) | |
| 5. | 3/30–4/17 | Recurrences and advanced counting techinques (Chapter 8) |
Resolve to work hard and get a good grade in this class.
Attend class. Arrive on time.
Do not bring distractions to class. If you read your email, listen to music, send and receive text messages or engage in other distracting activities during class, you will get very little out of class. That will show up in your grade.
Ask questions in class. If you do not understand something, ask a question about it.
Ask questions outside of class. If you have a question about an assignment, ask.
Please use a subject indicating that you are asking a question for CSCI 2405, and always include your name in your email. A reasonable subject for a question about assignment 3 is
CSCI 2405 questionPlease send email to the address listed on the first page of this syllabus. Do not expect immediate answers. Give yourself time to get answers.
Schedule time to work outside of class.
Get adequate sleep. Sleep is important both before and after you learn new concepts. Sleep before enables you to concentrate and think clearly, and sleep afterwards is critical for moving new information into permanent memory.
For information about
please see the auxiliary information at http://www.cs.ecu.edu/~karl/2405/spr20/syllabus-aux.html.