CSCI 3680 Course Syllabus

Discrete Structures in Computer Science

Fall 2024

 

 

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

Telephone:      (478) 445-5483
Email:              jf.yao@gcsu.edu
URL:              https://abacus2.gcsu.edu  (ignore the security warning.)

 

Office Hours (Face to Face in Atk317 or via Microsoft Team):

07:50 AM – 09:20 AM, Tuesday and Thursday

08:00 AM – 10:00 AM, Wednesday

and by appointment (via email: jf.yao@gcsu.edu)

 

LOCATION
            2:00PM – 3:40PM; T, R (ATK 310)

REQUIRED TEXT:

“Mathematical Structures for Computer Science –Discrete Mathematics and Its Applications”, seventh Edition, 2014, by Judith Gersting.   

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

COURSE OBJECTIVES:

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

COURSE DESCRIPTION :
This course offers an intensive introduction to discrete mathematics as it is used in computer science. Topics include functions, relations, sets, propositional and predicate logic, simple circuit logic, proof techniques, cryptography, discrete probability, graphs and trees, and understanding of basic Finite-State Machines, Turing Machines, and Formal Languages.

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.
  • 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, and the average case analysis of algorithms.
  • Understand hashing function and hashing.
  • Understand cryptography
  • Understand basic graphs and Trees
  • Understand basic Finite-State Machines, Turing Machines, and Formal Languages

 

SATISFIED PROGRAM STUDENT OUTCOMES:

·         SO1: Apply computer science theory and software development fundamentals to produce computing-based solutions.

 

GRADE DISTRIBUTION:
                                Percentage           Date
Weekly Quiz               40%                 Tuesday

Exam I                         30%                 Oct. 03, 2024
            Exam II                       30%                 Nov. 21, 2024

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

GRADEING POLICY:
      Grade              Percentage
        A                90% and up
        B                80% - 89.99%
        C                70% - 79.99%
        D                60% - 69.99%
        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 quiz or an exam unless you have a verifiable excuse.  An unexcused absence from a test will result in a numerical grade of zero for that test.

·         Your grades are updated on a regular basis on D2L throughout the semester.    

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 in the Undergraduate Catalog.

 

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           Proof Techniques

Week Five           Induction Recursion and Recurrence Relations, Analysis of Algorithms

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

Week Seven         Relations, Topological Sorting, Relations & Databases

Week Eight          Relations, Topological Sorting, Relations & Databases

Week Nine           Functions, Matrices

Week Ten            Graphs and Their Representations, Trees and Their Representations

Week Eleven       Graphs and Their Representations, Trees and Their Representations

Week Twelve       Decision Trees, Huffman Codes

Week Thirteen     Computation, and Languages

Week Fourteen    Finite-State Machines

Week Fifteen       Turing Machines

Week Sixteen      Formal Languages 

REQUIRED SYLLABUS STATEMENTS:

·         https://www.gcsu.edu/required-syllabus-statements-registrar

 

 

NOTE:

08/23/2024                  @ 5pm, Drop/Add Deadline without any record

10/14-15/2024             Fall Break

10/17/2024                  The last day to drop a course or withdraw from all courses with a W grade (unless previously assigned an F by the instructor or if the maximum number of dropped courses has been exceeded)

11/27-29/2024             Thanksgiving Holidays (No classes, campus closed)

12/09/2024                  The last day of classes