CS381 Introduction to Discrete Structures
Spring 2010


  • Instructor:

  • Instructor:  Professor Olariu,  E&CS building, Room 3300
  • TA/Grader: Samy E-Tawab,  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.

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 PL94-142 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.


  • Two intermediate in-class 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 right-hand corner of your homework. Staple all pages together and be sure that your name appears on every sheet.

Office Hours:  MW 1:00-2:00


Course Objectives:
The main objectives of this course are

to learn basic mathematical concepts such as sets, relations, functions, and graphs, relationships between them, and their properties,
to learn to reason correctly,
to learn techniques for solving problems,
to cultivate the ability to extrapolate, and
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 in-depth 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


Copyright 2010 - CS381