CSCI12680 Course Syllabus

Discrete Structures in Computer Science, Spring 2010

PROFESSOR INFORMATION
Name:              Dr. Yao
Office:             Atkinson Hall 317

Telephone:      (478) 445-5483
Email:              jf.yao@gcsu.edu
URL:               http://abacus2.gcsu.edu/
Office Hours:  8:25a.m.--9:25a.m. and 12:20p.m.--1:50p.m. on Tu. and Th.;  or by appointments

   -online office hours will be held at the same time
   -non-urgent emails will be answered at the same time

LOCATIONS
Classroom: Atk 104

REQUIRED TEXT:

Mathematical Structures for Computer Science – A Modern Treatment of Discrete Mathematics, sixth Edition, 2006, by Judith Gersting.   

PREREQUISITE: C or better in MATH 1113 and CSCI 1302.

COURSE OBJECTIVES:

This course serves the objective of learning an intensive introduction to discrete mathematics as it is used in computer science.

EXPECTED COURSE OUTCOME:

Students will be able to:

• Explain with examples the basic terminology of functions, relations, and sets.
• Perform the operations associated with sets, functions, and relations.
• Relate practical examples to the appropriate set, function, or relation model, and interpret the associated operations and terminology in context.
• Demonstrate basic counting principles, including uses of diagonalization and the pigeonhole principle.
• Apply formal methods of symbolic propositional and predicate logic.
• Describe how formal tools of symbolic logic are used to model algorithms and real-life situations.
• Use formal logic proofs and logical reasoning to solve problems such as puzzles.
• Describe the importance and limitations of predicate logic.
• Outline the basic structure of and give examples of each proof technique described in this unit.
• Discuss which type of proof is best for a given problem.
• Relate the ideas of mathematical induction to recursion and recursively defined structures.
• Identify the difference between mathematical and strong induction and give examples of the appropriate use of each.
• Apply the tools of probability to solve problems such as the Monte Carlo method, the average case analysis of algorithms, and hashing.
• Understand basic graph and Trees
• Understand basic Finite-State Machines, Turing Machines, and Formal Languages

COURSE DESCRIPTION :
Topics include propositional and predicate logic, functions, relations, sets, simple circuit logic, proof techniques, elementary combinatorics, and discrete probability.

ACADEMIC HONESTY:

The integrity of students is a critical component of the academic process.  All written work submitted in this course must be individual work unless the instructor assigns a team of students to work on an assignment.  Students must properly document all outside sources used for projects, programs, and homework. The submission of another’s work as one’s own is plagiarism, and will be dealt with using the procedures outlined on the Undergraduate Catalog.

EXAMS:
Percentage Date
            Weekly Quiz 50%                 Every Thursday

Mid-term exam 20% March 2, 2010 (Tu)
            Final Exam 30%                 May 4, 2010 (14:00-16:45, Tu.)

        ------------------------------------------------------------------------------------------
         Total                           100%

Note: The Homework material will be included in the exams.

FINAL GRADES:
      Grade              Percentage
        A                90% and up
        B                80% - 89.999%
        C                70% - 79.999%
        D                60% - 69.999%
        F                59.999% or less 

 COURSE POLICY:

• You are expected to read the textbook prior to and after class.
• Class participation is essential in learning computer technology.  It is your responsibility to attend the class in order to achieve good learning, therefore obtain a good grade. 
• You must NOT miss a test unless you have a verifiable excuse.  An unexcused absence from a test will result in a numerical grade of zero for that test.
• Prior to mid-semester, you will receive feedback on your academic performance in this course.  Your overall grades are updated on a regular basis on the Web throughout the semester.  

TENTATIVE COURSE OUTLINE:

Week One             Formal Logic: Statements, Symbolic Representation, and Tautologies

Week Two            Formal Logic: Propositional Logic, Quantifiers, Predicates, and Validity

Week Three         Formal Logic: Predicate Logic, Logic Programming, Proof of Correctness

Week Four           Recursion and Recurrence Relations, Analysis of Algorithms

  Week Five          Sets, Counting, Principle of Inclusion and Exclusion, Pigeonhole Principle

Week Six              Relations, Topological Sorting, Relations and Databases

Week Seven         Relations, Topological Sorting, Relations and Databases

Week Eight           Functions, Matrices

Week Nine           Graphs and Their Representations, Trees and Their Representations

Week Ten             Graphs and Their Representations, Trees and Their Representations

Week Eleven        Decision Trees, Huffman Codes

Week Twelve        Boolean Algebra and Computer Logic

Week Thirteen      Modeling Arithmetic, Computation, and Languages

Week Fourteen     Finite-State Machines

Week Fifteen        Turing Machines

Week Sixteen       Formal Languages

Week Seventeen   Proof Techniques, Induction

Class end on May 3, 2010

Martin Luther King Day: Jan. 18,  2010

Spring Break (March 22-26)

March 8, 2010 is the last day to drop without academic penalty.

FIRE DRILL PROCEDURE

In the event of a fire alarm signal students will exit the building in a quick and orderly manner through the nearest hallway exit.  Learn the floor plan and exits of this building. Do not use elevators.  Crawl on the floor if you encounter heavy smoke. Assist disabled persons and others if possible without endangering your own life. Assemble for a head count on front lawn of main campus.