WILLIAMPATERSONUNIVERSITY OF NEW JERSEY
COLLEGE OF SCIENCE AND HEALTH
Computer Science Syllabus and Outline
1. / Course: CS260-01 Discrete Structures, 3 credits (Major core course)
2. / Department secretary: Carol Parken (Coach House 120) can be contacted by telephone at (973)_720-2649 and by e-mail .
3. / Semester offered: Fall 2007
Time: Monday & Wednesday 8:00AM-9:15AM Location: Coach House T101B.
4. / Faculty: Dr. John Najarian, Prof. of Computer Science
Office: Coach House 201, Phone: (973)-720-3383, E-mail:
Office Hours: Monday & Wednesday 9:30AM - 10:45AM.,
Tuesday 6:00PM - 6:45PM and also by appointment.
5. / Required Text:
Susanna S. Epp [2004], Discrete Mathematics with
Applications,(3rd edition), Brooks/Cole (An International Thomson Company, ISBN: 0534359450).
Optional workbook:
Seymour Lipschutz and Marc Lipson [1997] Discrete Mathematics, (2nd edition),
Mc Graw Hill, Inc. (ISBN 0-07-038045-7) /
Resources (besides handouts and slides) :
(1) Susanna Epp’s book’s Thomson website (with Chapter, Book, & Course Resources):

(2) Susanna Epp’s edu booksite (nice applets and errata sheets):

…
Sites of lower priority:


Suggested Readings: (not required)
  • Alfred Aho and Jeffrey Ullman, Foundations of Computer Science, Computer Science Press, 1992.
  • Vangalur S. Alagar, Fundamentals of Computing: Theory and Practice, Prentice Hall, 1989.
  • Michael Albertson & Joan Hutchinson, Discrete Mathematics with Algorithms, Wiley, 1988.
  • Dexter J. Booth, Foundations of Discrete Mathematics for Computing, Chapman & Hall, ISBN: 0412562804, June 1995.
  • Hans Kleine Buning and Theodor Lettman, Propositional Logic: Deduction and Algorithms,CambridgeUniv. Press, 1999.
  • C.S. Calude (editor), People & Ideas in Theoretical Computer Science, Springer Verlag, ISBN 981402113X, 1999. (historical & biographical perspective)
  • Neville Dean,Essence of Discrete Mathematics (Essence of Computing), Prentice Hall, 1996.
  • Peter Fletcher, H. Hoyle, & Wayne Patty, Foundations of Discrete Mathematics, PWS-Kent, 1991.
  • G.P. Gavrilov and A.A. Sapozhenko, Problems and Exercises in Discrete Mathematics, (Kluwer Texts in the Mathematical Sciences, Vol 14), Kluwer Academic Pub, 1996.
  • Judith L. Gersting, Mathematical Structures for Computer Science, Computer Science Press, 1993.
  • Arthur Gill, Applied Algebra for the Computer Scientist, Prentice Hall, 1976.
  • Edgar Goodaire & Michael Parmenter, Discrete Mathematics With Graph Theory, Prentice Hall, 1997.
  • Ronald Graham, Donald Knuth, and Oren Patashnik, Concrete Mathematics: A foundation for Computer Science, Addison Wesley, 1989.
  • Winfried Karl Grassmann and Jean-Paul Tremblay, Logic and Discrete Mathematics : A Computer Science Perspective, Prentice Hall, 1996. (strong on logic, Prolog, and Miranda)
  • David Gries and Fred B. Schneider, A Logical Approach to Discrete Math, Springer-Verlag, 1993.
  • Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, Addison-Wesley, 4th edition, 1998.
  • M. Habib and C. McDiarmid (editors), Probabilistic Methods for Algorithmic Discrete Mathematics, (Algorithms and Combinatorics, 16), Springer-Verlag, 1998.
  • Cordelia Hall and John O'Donnell,Discrete Mathematics Using a Computer, Springer Verlag, 2000.
  • James L. Hein, Discrete Structures, Logic, and Computability, (Computer Science),
    Jones & Bartlett Pub., 1995.
  • Tor Helleseth and Harald Niederreiter, Sequences and Their Applications: Proceedings of Seta'98 (Discrete Mathematics and Theoretical Computer Science), Springer Verlag, 1999.
  • M. Huth and M. Ryan, Logic in Computer Science, CambridgeUniversity Press, 2000.
  • Richard.Johnsonbaugh, Discrete Mathematics, 4th edition, Macmillan Pub.Co.1996.
  • Bernard Kolman, Robert C. Busby, Sharon, and Cutler Ross, Discrete Mathematical
    Structures, 1999, Prentice-Hall
  • Seymour Lipschutz, and Marc Lipson, Schaum's Outline of Theory and Problems of Discrete Mathematics, McGraw-Hill, 1997.
  • Stephen Maurer and Anthony Ralston, Discrete Algorithmic Mathematics, Addison Wesley, 1991.
  • Joe Mott, Abraham Kandel, and Theodore Baker, Discrete Mathematics for Computer Scientists and Mathematicians, 2nd edition, Prentice Hall, 1986.
  • John E. Munro, Discrete Mathematics for Computing, Chapman & Hall, 1992.
  • Fletcher R. Norris, Discrete Structures : An Introduction to Mathematics for Computer Science, Prentice Hall, 1985.
  • Victoria Ossipova, Introduction to Discrete Mathematics: With Complete Software,
    ISBN: 1885978006, 1995.
  • R.C. Penner, Discrete Mathematics Proof Techniques and Mathematical Structures, World Scientific Pub Co., 1999.
  • Mike Piff, Discrete Mathematics: Introduction for Software Engineers, CambridgeUniv. Press, 1991.
  • Ronald E. Prather, Elements of Discrete Mathematics, Houghton Mifflin, 1986.
  • Ronald E. Prather, Discrete Mathematical Structures for Computer Science, Houghton Mifflin, 1976. (a classic)
  • Kenneth H. Rosen [2003]Discrete Mathematics and Its Applications, (5th edition),
    Mc Graw Hill, Inc.
  • Kenneth H. Rosen, John Michaels, and Jonathan Gross (editors), Handbook of Discrete and Combinatorial Mathematics, CRC Press, ISBN: 0849301491, 1999. (the reference).
  • Gunther Schmidt and Thomas Strohlein, Relations and Graphs : Discrete Mathematics for Computer Scientists, Springer Verlag, 1993.
  • Angela Shiflet, Discrete Mathematics for Computer Science, West Information Pub., 1987.
  • Donald Stanat & David McAllister, Discrete Mathematics in Computer Science, Prentice Hall, 1977.
  • J. K. Truss, Discrete Mathematics for Computer Scientists, Addison-Wesley, 1999.

6. / Course Objectives:
DESCRIPTION OF THE COURSE: : Topics include elementary propositional and predicate logics; elementary set theory; relations and their properties; functions; congruences and Euclidean algorithm; combinatorics; mathematical reasoning; matrices; elements of graph theory; trees and their applications; Boolean algebra. Some programming will be required.
COURSE OBJECTIVES:
1. To emphasize mathematical reasoning: Students must understand mathematical reasoning in
order to read, comprehend, and construct mathematical arguments.
2. To provide the ability to use combinatorial analytic methods.
3. To teach students how to work and model with discrete structures
4. To show the applications of discrete mathematics
5. To emphasize algorithmic thinking.
7. / Student learning outcomes:
Upon completion of this course, students will:
  1. Be capable of formulating models and theoretical constructs needed to make further progress in Computer Science..
  2. Be able to operate proficiently with these fundamental logical, combinatorial, and algebraic representations and tools in a manner required by and with a strong emphasis on Computer Scientific directions of development. Extensive practice and rigorous problem-solving drills will characterize the level of performance and expertise students will be acquiring.
  3. Through classroom participation in problem-solving sessions and discussions, homework, papers, and other assignments, this course also reinforces the following student learning outcomes in accordance with the university:

1) Effectively express themselves in precise written and oral form, both in the conciseness of mathematical formulation, first-order predicates, and in the modern standard prose.
2) Demonstrate the ability to think critically and logically. Students will be capable of developing rigorous (though fundamental) mathematical proofs (on their own). They will be capable of reasoning through several methods of inference including direct, indirect, by-contradiction, enumerative, and other methods. They will be expected to formulate problems and reason by the application of both propositional and predicate logic.
3) Locate and use information in the process of solving problems.
4) Demonstrate the ability to integrate knowledge and ideas in a coherent and meaningful manner.
8. / Topical outline of the course content (Based on 14 week model) Chapter
Session Number and Topic (Schedule) / Readings
1. / 1 Logic: Propositions, Truth Tables, Equiv, Taut, Imply
2 Logic: Laws, Basic Arguments, Truth,Boolean Algebra,
Circuit Design
/ Epp 1
Epp 1
Lipschutz 4, 15
2. / 3 Review
4 Quiz # 1 Foundations of Reasoning / Epp 1,
Epp 1,
3. / 5 Logic: Quantifiers, Predicates, Tarski’s World
6 Basics of PredicateLogic, Rudiments of Prolog / Epp 2
Epp 2, Lipschtz 4
4. / 7 Integers & Algorithms over them(+, *, mod, gcd, lcm, primality,
Euclidean Algorithm); Elementary Number Theory..
8 Proof Methodology: Inference Rules & Proof Strategy
Proof Methodology: (Principles &Basic Method) / Epp 3
Lipschutz 11
Epp 3
5. / 9 Quiz # 2 Predicates, Proofs and Number Theory
10 Vectors & Matrices (Fundamentals),
Introduction to Mathematical Induction
/ Handouts, Lipshtz 5, Epp 4
6. / 11 Sequences And Basics of Mathematical Induction.
Proof by Mathematical Induction.
12Sets, Notation, Basic Definitions of Set Theory. Properties of Sets.
Set Algebraic Proofs, Disproofs, and Boolean Algebras
Subsets, U, ∩ -, Venn Diagrams,Cartesian Product, Power Sets / Epp 4
Lipschutz 1.11
Epp 5
Epp 5
Lipschutz 1
7. / 13 Quiz # 3 Matrices, Induction, and Sets
14 Combinatorics: Counting, Decision Trees, Rule of Products,
Pigeonholes,Permutations and Combinations, Inclusion-Exclusion / Epp 6
Lipschutz 6
8. / 15 Combinatorics: Examples and Practice.
16 Basics of Discrete Probability (not abstract, nor theory),
Expected Value, Conditional Probability, Independence / Epp 6
Epp 6
Lipschutz 6, 7
9. / 17Quiz #4Combinatorics& Probability
18 Functions on a Set, One-to-One (injection) and Onto (surjection),
1-1 correspondence (bijection), Inversefunction, Composition. / Epp 6
Epp 7
Lipschutz 3
10. / 19 Functions: more examples. Graphs of functions.
20 Recursion (Basics), recursion in programming (factorial, fib, Hanoi) / Epp 7
Epp 8
11. / 21 Algorithms & Complexity: Measures, Search, Sort
22 Quiz # 5 Functionsand Recursion / Epp 9,
Lipschutz 3.8-3.9
12. / 23 Relations: Basics, Representation, Graphs, Relation Matrices
24 Relations: Properties, Equiv. Relations, Partial Orders / Epp 10
Epp 10, Lipschtz 2
13. / 25 Graphs: Def., Representation, Isomorphism, Paths vs Cycles,
Connectivity, Euler vs Hamilton, Computer Rep., Algorithms
26 Tree Theory: Concepts, Applications, Binary Trees, Expressions,
Spanning Trees; Minimal S.T. (Cheapest Railroad/Ethernet)
/ Epp 11
Lipschutz 8, 9
Epp 11
Lipschutz 10
14. / 27 Quiz # 6 Relations, Trees, & Graphs
28 Final Exam / Epp 11
9. / Teaching methods (e.g., lecture, discussions, presentations, etc.)
a) Classroom lectures, discussions, and problem solving sessions
b) Homework reviews
c) Lab work
10. / Course expectations:
a. Reading Assignments
Item 8 (above) addresses the reading schedule issue.
Spend at least two hours of time on reading and homework for every hour in class.
Weekends are review time above and beyond (independent of) this 2-for-1 rule.
b. Tentative timeline for submission of written assignments or other work
Projects will be collected as scheduled with a grace period of one week.
c. Attendance
Attendance will be recorded. Departmental guidelines require
that: 3 absences (2 for night) --- departmental warning letter
7 absences (4 for night) --- automatic failure in course
Only valid excuses (in writing) allay these consequences.
Attendance and success coincide.
d. Examinations (tentative dates, make-up policy, etc.)
All exams will be announced at least one full week in advance.
If you are absent on the day an exam is announced, you are responsible for finding out
about it from a fellow student or the professor. No make-up exams will be given except for
extraordinary circumstances.
Item 8 (above) addresses the examination schedule issue.
Final Exam. Period: Monday12/17/2007 at 8:00AM - 10:30AM, T101B
e. Class participation
Bring the specified textbook to each class session.
Before lab sessions and lectures, read relevant text to optimize productivity.
11. / Grading and other methods for assessing student academic performance:
  • 6 periodic quizzes (as specified above in the “Topical Outline”)
  • The lowest quiz grade will be dropped.
  • If you miss a quiz, that is the one which is dropped.
  • Final examinationis as scheduled by administration (date cited above).
  • Computation: Final Grade = Average of6 Quizzes and Final (80%)+
    Classwork/Homework/Projects (20%)

12. / Additional information:
Last day for course withdrawal Wednesday, 10/24/2007.
Classes will be in session from 9/5/2007 to 12/13/2007.
Holidays: 11/22/2007 – 11/25/2007 Thanksgiving Day (Thursday-Sunday).