CPSC 3115. Discrete Structures in Computer Science
Instructor
Dr. Edward L. Bosworth
Center for Commerce and Technology 443
(706) 565-4128
e-mail:
bosworth_edward@colstate.edu
website:
http://csc.colstate.edu/bosworth/
Office Hours:
Monday: 3:00 PM to 5:00 PM 2.0 hours
Tuesday: 9:30 AM to 12:00
Noon 2.5 hours
3:00 PM to 4:00
PM 1.0 hour
Wednesday: 10:30 AM to 12:00
Noon 2.5 hours
3:00 PM to 4:00
PM 1.0 hour
Thursday: 9:30 AM to 11:00 AM 1.5 hours
Friday: No office hours on Friday. Contact me via e–mail.
I am available to speak with
students any time that I am in my office.
Please note that faculty meetings are
frequently scheduled for 12:30 PM on Wednesdays and Thursdays.
Class Meetings: To
be scheduled later.
Course Description
A mathematical study of the underpinnings of computational devices and modern computers.
Introduction to Boolean algebra and the logic gates used to
implement Boolean functions.
Methods to reduce the complexity of Boolean functions, including simple
algebra, Karnaugh
Maps, and the Quine-McClusky method. Introduction to flip-flops and sequential
logic.
Study of Finite-State Machines (FSM), including Moore machines and Mealy
machines, such
as counters and sequence detectors. Use
of FSM in modeling protocols, including the TCP
used on the Internet. Introduction to
classes of automata (FSM, pushdown automata, linear
bounded automata, and Turing machines) and associated types of grammar
(regular, context-
free, context-sensitive, and phrase-structure).
Basic study of the Backus-Naur form.
Course Prerequisites
MATH 1131 – Calculus with
Analytic Geometry I
CPSC 1301 – Computer Science 1
Required Textbook
None
The course will be taught
entirely from notes by the instructor.
These notes are available at
the CSU bookstore or on the web.
Course Objectives (Learning Outcomes)
At the end of the course the student will have an understanding of:
1) The
basics of mathematical graph theory and its uses in defining network topology.
ABET Criteria Addressed: A, C, J
Program Objectives Addressed: 1, 2
2) The
use of probabilistic graphs to assess the reliability of networks with
components that are prone to
failure.
ABET Criteria Addressed: A, C, J
Program Objectives Addressed: 1, 2
3) The
definition of a subgraph, the difference between induced and non–induced
subgraphs, and methods to
determine the count of each in a given graph.
ABET Criteria Addressed: A, C, J
Program Objectives Addressed: 1, 2
4) Theoretical
and experimental approaches to optimization of subgraph counts.
ABET Criteria Addressed: A, C, J
Program Objectives Addressed: 1, 2
5) An
understanding of the basics of finite-state machines (FSM) including Mealy
and Moore machines.
ABET Criteria Addressed: A, C, J
Program Objectives Addressed: 1, 2
6) The
use of FSM in modeling protocols, such as TCP.
ABET Criteria Addressed: A, C, J
Program Objectives Addressed: 1, 2
7) The
basic classes of computation devices and the grammar recognized by each.
ABET Criteria Addressed: A, C, J
Program Objectives Addressed: 1, 2
8) The
use of Backus-Naur form (BNF) to describe context-free grammars.
ABET Criteria Addressed: A, C, J
Program Objectives Addressed: 1, 2
9) The
issues that are addressed by the theory of computability.
ABET Criteria Addressed: A, C, J
Program Objectives Addressed: 1, 2
Course Methods
This will be an in-class lecture course, taught face-to-face.
There might be programming
assignments, but no lab assignments.
Methods for Evaluating Students
The evaluation methods will include homework, a mid-term exam, and a final exam.
Homework Policy
All homework is due at the beginning of the class on
the day assigned. Homework handed
in after the start of class will be considered to be late. The penalty for late homework (if
assessed) will be 10 points per class period.
Homework submitted after the solution has
been discussed in class will be returned ungraded and cannot receive credit.
Methods for
Evaluating Students
Homework 40%
Mid-Term Exam 30%
Final Exam 30%
Assignment of Letter
Grades
The method of assigning letter grades based on overall
course averages is fairly standard.
The basic method is described as follows:
GRADE POINTS
A 90 – 100 D 55 – 69
B 80 – 89 F Below 55
C 70 – 79
Policy on Tests and
Final Exams
All in-class quizzes and tests (but not the final exam) will
be graded and returned on the
following class period. The class
meeting immediately preceding the test is devoted to
review for the test, and the class period immediately following the test is
devoted to return
of the test and discussion of all test questions and possible answers.
For all in-class quizzes and tests (but not the final exam),
the deadline for requesting a
review of the grade is either two weeks after the test is returned or one week
before the
scheduled date for the final exam, whichever date is earlier.
Please note that a grade review will never lead to reduction of an assigned grade.
Typical Course Schedule
The course will cover the following topics in approximately this order.
Basic Definition of Terms
Elementary set theory and
basic operations: Intersection, Union, Difference, etc.
Introduction to Graph Theory
Definition of graphs in terms of set theory and more
obvious diagrams.
Directed and undirected
graphs.
Basic terminology used in
discussion of graphs.
Trees, spanning trees, and a
few theorems on trees.
Bipartite graphs, complete
graphs, and complete bipartite graphs.
Induced subgraphs and ways to
count them.
Weighted graphs and their
uses.
Minimum spanning tree
algorithms.
Distances between vertices in
a graph.
Connectivity and application
to networks.
Breadth-First Search and
Depth-First Search.
Graphs
and Computer Networks
Computer networks as nodes connected by communicating links
Network topologies and their
representation by graphs.
Probabilistic graphs and
network reliability under component failure.
Optimization of network
reliability measures.
Network reliability measures
and counting subgraphs.
Counting Subgraphs
Induced and non–induced
subgraphs.
Counting these subgraphs.
Optimizing graphs with
respect to counts of three–vertex subgraphs.
Theoretical limits on the
counts of three–vertex subgraphs.
Known optimality results for
three–vertex subgraphs.
Computational Approaches to Graph Optimality
Comparison of theoretical
and experimental approaches to graph optimality.
Experimentation as a method
for disproof.
Options for generating and
evaluating candidate graphs.
Genetic algorithms as a basis
for generating candidate graphs.
Introduction to Finite-State Machines (FSM)
Sample FSM, including traffic lights and vending
machines
Modulo-N counters: up
Counters and up-down counters
Sequence detectors.
Theory of Finite Automata (FA)
New terminology for discussion of Finite State Machines.
A sequence detector presented
in the language of finite automata.
Formal definition of a finite
automaton.
Strings accepted by the FA
and languages recognized by the FA.
Algorithmic simulation of a
finite automaton.
Finite-state machine models:
Moore and Mealy machines.
The sequence detector as
equivalent to a language recognizers.
Finite-state-machine models
of vending machines.
Applications of Finite State Machines
Finite-state machine models of job scheduling by an
Operating System.
Finite automata as models
of computer network protocols.
Language Recognition and Grammars
Basic definitions of a grammar: symbols, alphabets,
strings, and languages.
The hierarchy of grammars and
languages.
Regular expressions.
Context-free grammars and
Backus-Naur form.
Context-sensitive and
phrase-structure grammars.
Turing Machines: Deterministic and Non-Deterministic
Definition of a Turing machine.
The Church/Turing thesis and why it cannot be proved.
The idea of a
non-deterministic Turing machine and how we use it.
Other Course Policies
I do not take roll, but believe that it is important for
students to attend class regularly. If
you
find it necessary to miss one or more classes, you are still responsible for
all material covered
in the class. You should notify me in
advance of expected class absences to avoid late
penalties on homework due on the date you miss.
For more information on class attendance
and withdrawal, refer to http://aa.colstate.edu/advising/a.htm#Attendance%20Policy.
Parking
Parking is a problem at CSU; for this we apologize. It is the student’s responsibility to arrive
at class on-time and submit any homework before the beginning of class.
If you have a documented disability as described by the
Rehabilitation Act of 1973 (P.L.
933-112 Section 504) and the Americans with Disability Act (ADA) that may
require you to
need assistance attaining accessibility to instructional content to meet course
requirements,
we recommend that you contact the Center for Academic Support at (706)568–2330,
as
soon as possible. It is then your
responsibility to contact and meet with the instructor.
It is also your responsibility to present the instructor with a letter
from the Center for
Academic Support. Without this
letter detailing the required accommodations, the
instructor cannot help you.
The Center for Academic Support can assist you and the
instructor in formulating a reasonable accommodation plan and provide support
in
developing appropriate accommodations for your disability. Course requirements will not be
waived but accommodations may be made to assist you to meet the
requirements. Technical
support may also be available to meet your specific need. For more information on services
and support available, refer to the web site for the Center for Academic
Support.
Dropping The Course
We hope that you will complete the course and profit from
it. If it is necessary for you to
withdraw from the course during the semester, you must follow all official CSU
procedures
for withdrawing. It is not sufficient to
notify the instructor; you must use the ISIS system
and withdraw officially. For details on
how to withdraw from a course, see the web page
http://aa.colstate.edu/advising/w.htm#Withdrawal%20from%20a%20Course.
I would appreciate it if you were first to consult with me
before starting the procedure for
withdrawing from the course. In some
cases, we can agree on an arrangement that will
allow you to complete the course with minor adjustments.
Academic dishonesty
Academic dishonesty includes, but is not limited to, activities such as
cheating and
plagiarism. It is a basis for disciplinary action. Collaboration is not permitted
on assignments
or exams/quizzes in this course. Any work turned in for individual credit must
be entirely the
work of the student submitting the work. All work must be your own. You
may share ideas
but submitting identical assignments (for example) will be considered cheating.
A simple
way to avoid inadvertent plagiarism is
to talk about the assignments, but don't read each
other's work or write solutions
together. Keep scratch paper and old versions of assignments
until after the assignment has been
graded and returned to you. If you have any questions
about this, please see me immediately.
For assignments, access to notes, textbook, books and other
publications is allowed. Stealing,
giving or receiving any code, diagrams, drawings, text or designs from another
person (CSU
or non-CSU) is not allowed. Having access to another person’s work on the
system or giving
access to your work to another person is not allowed. It is your responsibility
to keep your
work confidential, so that other students do not have access to it without your
knowledge.
Properly dispose of all your scratch work.
No cheating in any form will be
tolerated. The penalty for the first occurrence of academic
dishonesty is a zero grade on the assignment or exam/quiz; the penalty for the
second
occurrence is a failing grade for the course. For exams/quizzes, discussion of
any kind
(except with me) is not allowed.
(http://aa.colstate.edu/advising/a.htm#Academic
Dishonesty/Academic Misconduct)