CS381
Introduction to Discrete Structures
Spring 2010
Syllabus

Instructor:

Instructor: Professor Olariu, E&CS building, Room 3300

TA/Grader: Samy
ETawab, E&CS building, Room 3300
Work hard:
Foremost, students are urged
to work hard! This class covers a lot of material in
a short amount of time – do not let yourself get
behind. Work hard and keep up the pace! In designing
this class, efforts have been made to assist
students in their learning by frequently allowing
them to exercise what they learn and quickly receive
feedback. The class is designed so that if you work
hard and keep up on things you can succeed.
As a corollary to working hard, please feel free to
ask the instructor questions, but please ponder,
read and reflect on your own before doing so.
Ask Questions and do
exercises:
It is students'
responsibility to make sure (ask questions and do
exercises) if they do not understand all the
lectures and materials. I will repeat and try as
much as I can to help you understand. It is not
acceptable that students state that they do not
understand the lecture or material at the end of
semester.
Policies
Students are responsible for
all material covered and announcements, policies,
and deadlines discussed in lecture, discussion
section as well as those posted on the website.
Disability Services
In compliance with
PL94142 and more recent federal legislation
affirming the rights of disabled individuals,
provisions will be made for students with special
needs on an individual basis. The student must have
been identified, as "special needs" by the
university and an appropriate letter must be
provided to the course instructor. Provisions will
be made based upon written guidelines from the
University’s Special Needs Students Resource Office.
All students are expected to fulfill all course
requirements.
Academic Integrity
By attending Old Dominion
University you have accepted the responsibility to
abide by the honor code. If you are uncertain about
how the honor code applies to any course activity,
you should request clarification from the
instructor. The honor code is as follows:
“I pledge to support the honor system of Old
Dominion University. I will refrain from any form of
academic dishonesty or deception, such as cheating
or plagiarism. I am aware that as a member if the
academic community, it is my responsibility to turn
in all suspected violators of the honor system. I
will report to Honor Council hearings if summoned."
Any evidence of cheating will result in a 0 grade
for the assignment/exam, and the incident will be
submitted to the department for further review.
Evidence of cheating may include a student being
unable to satisfactorily answer questions asked by
the instructor about a submitted solution. Cheating
includes not only receiving unauthorized assistance,
but also giving unauthorized assistance.
Submitting anything that is not your own work
without proper attribution (giving credit to the
original author) is plagiarism and is considered to
be an honor code violation. It is not acceptable to
copy written work from any other source (including
other students), unless explicitly allowed in the
assignment statement. In cases where using resources
such as the Internet is allowed, proper attribution
must be given.
Students may still provide legitimate assistance to
one another. You are encouraged to form study groups
to discuss course topics. Students should avoid
discussions of solutions to ongoing assignments and
should not, under any circumstances, show or share
code solutions for an ongoing assignment.
Please see the ODU Honor Council’s webpage at
http://orgs.odu.edu/hc/ for other concrete examples
of what constitutes cheating, plagiarism, and
unauthorized collaboration. All students are
responsible for knowing the rules. If you are
unclear about whether a certain activity is allowed
or not, please contact the instructor.
Grading:
 Two intermediate inclass
tests, each 20%
 Six assignments 30%
 Final examination 30%
Homework assignments
Homework will be turned in
based on due time. Homework is due at the
beginning of class (or discussion section) the day
it is due. At the beginning means before of
class.
You must work alone on your homework. You
must write your name and university ID number in the
upper righthand corner of your homework. Staple all
pages together and be sure that your name appears on
every sheet.
Office Hours: MW
1:002:00
Course Objectives:
The main objectives of this course are
 1.
 to learn basic mathematical concepts such as
sets, relations, functions, and graphs,
relationships between them, and their
properties,
 2.
 to learn to reason correctly,
 3.
 to learn techniques for solving problems,
 4.
 to cultivate the ability to extrapolate, and
 5.
 to become proficient in using mathematical
notations (both in reading and writing).
Course Contents:
First we learn a general methodology for solving
problems. This methodology is going to be followed
in solving problems, and in proving theorems
throughout this course.
The next subject is logic. It is
covered in Chapter 1 of the textbook. It is a
language that captures the essence of our reasoning,
and correct reasoning must follow the rules of this
language. We start with logic of sentences called
propositional logic, and study elements of logic,
(logical) relationships between propositions, and
reasoning. Then we learn a little more powerful
logic called predicate logic. It allows us to reason
with statements involving variables among others.
In Chapter 2, we also study sets,
relations between sets, and operations on sets. Just
about everything is described based on sets, when
rigor is required. It is the basis of every theory
in computer science and mathematics.
In Chapter 4, we learn recursive
definitions and mathematical reasoning, in
particular induction. There are sets, operations and
functions that can be defined precisely by recursive
definitions. Properties of those recursively defined
objects can be established rigorously using proof by
induction.
Then in Chapters 8 we study
relations. They are one of the key concepts in the
discussion of many subjects on computer and
computation. For example, a database is viewed as a
set of relations and database query languages are
constructed based on operations on relations and
sets. Graphs are also covered briefly here. They are
an example of discrete structures and they are one
of the most useful models for computer scientists
and engineers in solving problems. More indepth
coverage of graph can be found in Chapter 9.
Finally, back in Chapter 2 again,
we briefly study functions. They are a special type
of relation and basically the same kind of concept
as the ones we see in calculus. However, it is one
of the most important concepts in the discussion of
many subjects on computer and computation such as
data structures, database, formal languages and
automata, and analysis of algorithms which is
briefly covered in Chapter 3.
Right to change
information
Although every effort has been made to be complete
and accurate, unforeseen circumstances arising
during the semester could require the adjustment of
any material given here. Consequently, given due
notice to students, the instructor reserves the
right to change any information on this syllabus or
in other course materials.
Back to
Main CS381
