Math-231
The Mathematics of Computer Science
Course Syllabus
August 29, 2008
INSTRUCTOR : Constantine Roussos
OFFICE : Hobbs 104
PHONE: 544- 8395 (office), 804-263-6692 (home)
================================================================================

Chapter

Week

Sections

Topic

Material Covered

End-of-Chapter Exercises

Tests

1

6

Foundations.  Set theory, logic, and algorithms.

Basic terminology used in set theory.  Statements, rules of inference proof techniques, general syntax for algorithms

Section 1.1 Pg 24-26 -odd/even

Section 1.2 Pg 43-44 -odd/even

Section 1.3 Pg 52 - odd/even

Section 1.4 Pg 62-63 - odd/even

Section 1.5 Pg 72-73 - odd/even

Section 1.6 Pg 86-87 - odd/even

 

2

5

Integers and Mathematical Induction

Properties of integers and principle of induction. Computer memory representation.  Proving correctness of programs.

Section 2.1 Pg 111 - odd/even

Section 2.2 Pg 133 - odd/even

Section 2.3 Pg 147-148 - odd/even

Section 2.4 Pg 162 - odd/even

Section 2.5 Pg 170 - odd/even

 

3

3

Relations and Posets

Relations, posets, and matrices, including graphical representation. 

-----------------------------------------

Section 3.1 Pg 205-207 - odd/even

Section 3.2 Pg 225-227 - odd/even

Section 3.3 Pg 234 - odd/even

 

 

Test #1

4

2

Matrices

Section 4.1 Pg 255-256 - odd/even

 

 

 

5

4

Function

Relationship between functions and strings.

Section 5.1 Pg 297-298 - odd/even

Section 5.2 Pg 314 - odd/even

Section 5.3 Pg 330-331 - odd/even

Section 5.4 Pg 339-340 - odd/even

 

7

8

Counting Principles

Addition, multiplication principle, pigeonhole principle, permutations, combinations, binomial coefficients, and discrete probability

Section 7.1 Pg 429-431 - odd/even

Section 7.2 Pg 437 - odd/even

Section 7.3 Pg 442 - odd/even

Section 7.4 Pg 447 - odd/even

Section 7.5 Pg 455 - odd/even

Section 7.6 Pg 468-469 - odd/even

Section 7.7 Pg 476 - odd/even

Section 7.8 Pg 487 - odd/even

 

8

3

Recurrence Relations

Counting techniques using recurrence relations.  Linear homogeneous recurrence relations and certain linear nonhomogeneous recurrence relations, especially as they relate to divide and conquer techniques.

Section 8.1 Pg 511-512 - odd/even

Section 8.2 Pg 527 - odd/even

Section 8.3 Pg 545 - odd/even

 

 

 

 

 

 

 

Test #2

9

2

Algorithms and Time Complexity

Big-O notation, theta notation.  Various classical algorithms.

Section 9.1 Pg 563-564 - odd/even

Section 9.2 Pg 599-600 - odd/even

 

Chapter

Sections

Topic

Material Covered

End-of-Chapter Exercises

Tests

10

7

Graph Theory

Basic graph theory definitions and terminology – subgraphs, walks, paths, circuits, isomorphism of graphs, planar graphs, and graph coloring.

Section 10.1 Pg 617-619 - odd/even

Section 10.2 Pg 634-635 - odd/even

Section 10.3 Pg 643 - odd/even

Section 10.4 Pg 660-661 - odd/even

Section 10.5 Pg 668-669 - odd/even

Section 10.6 Pg 684 - odd/even

Section 10.7 Pg 701-702 - odd/even

 

11

4

Trees and Networks

Trees, special types of trees, determining spanning and minimal spanning tree.  Transport networks, including maximal flow.

Section 11.1 Pg 711-712 - odd/even

Section 11.2 Pg 730-731 - odd/even

Section 11.3 Pg 742-743 - odd/even

Section 11.4 Pg 766 - odd/even

 

 

 

 

 

 

Test #3

12

3

Boolean Algebra and Combinatorial Circuits

Boolean algebra and its application in design of switching and digital circuits

Section 12.1 Pg 784-785 - odd/even

Section 12.2 Pg 794 - odd/even

Section 12.3 Pg 822-823 - odd/even

Chapter #13 - Optional

13

3

Finite Automata and Languages

Introduction to automata theory and languages.

Section 13.1 Pg 849-851 - odd/even

Section 13.2 Pg 859-860 - odd/even

Section 13.3 Pg 873 - odd/even

 

 

 

 

Final Exam

================================================================================

Testing
There will be 3 tests, an undetermined number of pop quizzes and homework assignments and a final exam. Class participation will also count towards one's grade.

The above factors will be weighted as follows :

Tests .51
Final Exam : .34
Class Partic, Homework, Quizzes: .15

Grading :
The standard 10 point grading scale will be used.
(i.e. 90-100 = A, 80-89 = B, 70-79 = C, 60-69 = D, below 60 = F)
THERE WILL BE NO CURVE. You will always know approximately how you are doing in the course by applying the above factors to your grades to date.

Important notes:

  1. If you are having trouble with the course come to me for help right away - DO NOT WAIT.
  2. You are responsible for attending class, completing assignments on time, taking tests when scheduled, knowing the College's grading policies, knowing course withdrawal dates and making up all missed work.
  3. As always, the honor code is in full effect. You may NOT collaborate on tests. You may NOT collaborate on projects and programs except as instructed by me. If you are ever in doubt of whether or not an action constitutes an honor violation ask me beforehand.
  4. Class participation on your part is an excellent means of making our classes more interesting and demonstrating to me your knowledge of and interest in the subject matter.

“The College will make reasonable accommodations for persons with appropriately documented disabilities.  Students should notify the Support Services Coordinator located in the Academic Advising Office on the first floor of Hall Campus Center and provide documentation of their disability in order to be considered eligible for accommodation.  Students are encouraged to do this as soon as possible prior to or at the beginning of each semester so their needs can be arranged in a timely fashion.  Accommodations are effective as of the date of the Accommodations Memos students receive to distribute to their instructors.  Accommodations are not retroactive


Top of this page   Top of page      Home page   Home page