| Class meeting |
3:00–3:50 MWF Brewster D304 |
|---|---|
| Instructor | Karl Abrahamson |
| Office | Sci&Tech C-113 |
| Office hours | MThF 11:00–12:00 and MW 4:00–5:00 or by appointment |
| Phone | 328-9689 |
| abrahamsonk@ecu.edu | |
| Course web page | www.cs.ecu.edu/~karl/2405/spr18/ |
| My web page | www.cs.ecu.edu/~karl/ |
| Textbook | Discrete Mathematics and Its Applications, seventh 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;
matrices;
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.
Peano induction. Strong induction.
Counting. Basic counting techniques. Permutations and combinations. The pigeonhole principle. Permutations and combinations. Inclusion-exclusion.
Linear recurrences. Recurrences for divide-and-conquer algorithms. Solving recurrences. Generating functions.
Graphs and trees. Properties of graphs and trees. Algorithms on graphs.
After successfully completing this course, students will have the following abilities.
Prove mathematical statements using Peano induction and strong induction.
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.
Apply generating functions to deriving the values of infinite sums.
Derive solutions to homogeneous and nonhomogeneous linear recurrences. Solve divide-and-conquer recurrences.
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.
There will be 4 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 be at 2:00–4:30 Monday, April 30. 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 homework assignments approximately weekly. All of the homework assignments and due dates are listed on the course web page.
Grades will be computed as follows. Percentages will be chosen from the given ranges to maximize your score.
| Grading | |
|---|---|
| 4 midterms | 25%–40% |
| A comprehensive final exam | 25%–35% |
| Homework | 20%–30% |
| Attendance | 10% |
You will start with 10 points for attendance and lose one point for each unexcused absence.
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.
You are expected to attend class. You are responsible for announcements and assignments given in class. If you miss a class, it is up to you to obtain notes and any other information that was provided in the class. Excuses that you did not know about something because you did not come to class and did not obtain the information will not count for anything at all.
Those who do not attend class can count on doing poorly in this course. If you choose not to attend class, then you must live with the consequences of that choice, however bad they are.
Even if you believe you already know what we are covering, come to class. If you don't, you will end up missing material that you did not know we were going to cover and you will fall behind.
If you are having trouble understanding the lectures, do not stop coming to class. Come to office hours. Get help as early as possible.
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/spr18/syllabus-aux.html.