Course Syllabus
Spring 2009 CpSc 311:  Discrete Computational Structures 
Instructor: Dr. David Dailey

Meeting Time: 11:00 - 11:50  (Period 4) - MWRF

Meeting Place: ATSH 224.

Instructor's Office Hours: Monday and Wednesday 9:00 a.m. - 10:00 a.m..; Tuesday  and Thursday 8:00 a.m. - 9:30 a.m.., or by appointment.

Instructor's Office location: ATSH 248

Instructor's phone and e-mail address: 738-2145 david.dailey@sru.edu

Assessment: The connection of course outcomes, with departmental outcomes and ultimately with university outcomes is discussed at some length at http://cs.sru.edu/~whit/assessment/.

Course Description: 

Introduces computational implementations of the mathematical structures most frequently used in computing including sets, equivalence relations, functions, graphs, trees and standard logic.  Also introduces automata, formal languages, countability, decidability and computational complexity, Markov and stochastic processes. The course will stress traditional programming and mathematical approaches to these structures such as the use of recursion, elementary data structures, and proof techniques to instantiate, parse, traverse, demonstrate correctness, or use these computational objects. Prereq: CpSc140, Math 120. (4 credit hours)

Objectives and/or competencies of proposed course:

The student will be able to:

1.      Define basic computational terms and perform computational operations associated with sets, functions, relations, trees, and graphs.

2.      Apply formal methods of symbolic logic and proof techniques used to solve traditional computing problems.

3.      Apply the tools of probability to solve problems.

4.      Evaluate the run-time performance of alternative algorithms.

5.      Model problems in computing using graphs, trees and Markov chains.

6.      Relate graphs and trees to data structures, algorithms and counting.

Evaluation procedures to be utilized:

The student will:

1. Complete homework paper-and-pencil assignments covering basic principles of discrete computational structures and their mathematical underpinnings.
2. Design, code and debug or modify programs in a computer language that illustrate discrete computational structures.
3. Complete examinations that assess understanding of the student of theoretical concepts studied including, possibly, mathematics preliminaries and their application in computing.

 Course activities: Course is designed as a traditional lecture course: at instructor’s discretion materials may include handouts, projected material (web, transparencies, presentation software), class discussion, guest lectures, etc.

Required text: Discrete Structures, Logic and Computability - James L. Hein, 2nd Edition, 2002, published by Jones and Bartlett Computer Science.

Required reading: Class web page found at http://srufaculty.sru.edu/david.dailey/cs311/index.htm

Computing labs: The class will primarily use equipment provided in  ATSH 224; other machines on campus may be used as well.

Software used:

Use of e-mail software is also required for most assignments (see below, under Assignments and tasks).

Method of determining final grade: Regular assignments: 50%; two quizzes,  each worth 15%; one final exam: 20%, due at time of last class meeting.

Final exam:  The course will have a final exam, as scheduled by the University.

Attendance policy: Regular attendance is expected. Excessive absences will have an effect on your grade. If a prolonged illness should cause you to miss several class periods, you are expected to discuss this with the instructor.

Late work: The grade on an assignment will be dropped by 20% if not submitted on time. Assignments more than three days late are not accepted without a physician's statement.

Make-up exams: It is the student's responsibility a) to notify the instructor beforehand if he or she must miss an exam due to illness, or family emergency and b) to take the initiative in finding a time suitable to the instructor for a make-up exam. Make-up exams should be scheduled within one week following the original exam date.

Academic Integrity: All academic work for this course must consist of your own work. See the University's statement on Academic Integrity in the Undergraduate Catalog (2003-04, pages 52 - 53). Though it remains the student's responsibility to read and understand the University's expectations here, I wish to emphasize the following excerpts from that statement:

"Academic dishonesty may take many forms. Examples of academic dishonesty include, but are not limited to, the following: (...)

• plagiarizing and/or submitting the work of another as your own;
• (...)
• any attempt, or actual, collusion willfully giving or receiving unauthorized or unacknowledged assistance on any assignment (both parties to the collusion are considered responsible.)"

The fact that this course is in Computer Science does not lessen the student's responsibility to make sure that work submitted for a grade is his or her own work. Again, from the University's statement on Academic Integrity:

• "All academic work, including, but not limited to, papers, computer programs, assignments, and tests, must consist of the students’ own work.
  
• Students are expected to learn and practice proper techniques for accurately citing resource material.
  
• Students are expected to be honest in all academic work, refraining from all forms of cheating.
  
• Students are expected to function as students, including, but not limited to, attending class regularly and completing all assignments and examinations."

Assignments and tasks: Each assignment will be explained in class. Any uncertainties students may have about an assignment should be raised at the time the assignment is made. Students will be required to use e-mail for certain assignments; assignments submitted via e-mail must follow the guidelines explained in class.

Several homework assignments will be given during the semester. Unless otherwise stated, these assignments are to be completed individually by each student. Students may be called upon to present and explain their work to the class or to the instructor and should be consistently and adequately prepared to do so.

As the semester progresses, additional details about assignments may be found on the class web page.

Tentative Schedule of Topics

Assignments shown may vary. Refer to lecture notes and/or course web-site for details.

Outline

I.                   Introduction

a.       Explain basic terminology

                                                              i.      Functions

                                                            ii.      Relations

                                                          iii.      Sets

                                                          iv.      Trees 

                                                            v.      Graphs

b.      Applicability to computing

                                                              i.      Functions

                                                            ii.      Relations - Equivalence relations, closures

                                                          iii.      Sets - Finite, countably infinite, uncountably infinite sets

                                                          iv.      Trees 

c.       Using structure in programs

                                                              i.      Functions

                                                            ii.      Relations

                                                          iii.      Sets

                                                          iv.      Trees 

II.                Formal Methodology

a.        Binary operators

b.      Symbolic logic

c.       DeMorgan’s laws

III.             Proof techniques

a.       Proof by induction

b.      Using proofs to solve problems such as puzzles

IV.             Demonstrate basic counting principles

a.       Diagonalization

b.      pigeonhole principle

V.                Relate the ideas of mathematical induction to recursion

VI.             Computing and analysis (3 hours)

a.        permutations of a set

b.      combinations of a set

c.       evaluate the run-time performance of alternative algorithms

VII.          Probabilities (3 hours)

a.       Discrete probabilities

b.      Distributions

c.       Monte Carlo method

VIII.       Apply the tools of probability to solve problems

a.       the average case analysis of algorithms

b.      hashing

IX.             Computational Complexity

a.       Asymptotic analysis of bounds

b.      Big-O, little-O

c.       Worst-case

d.      Best Case

e.       Average case

f.       Time-Space trade-offs

g.      Recurrence relations

X.                Introduction to Graphs and Trees

a.       Binary Search Tree

b.      Spanning Trees

c.       Shortest Path

d.      Undirected graphs

e.       Directed graphs

XI.             Graphs

a.       Cycles

b.      Traversability

c.       Connectedness

d.      Distance

XII.          Traversal methods

a.       Demonstrate and implement tree traversals

b.      Demonstrate and implement graph traversals

XIII.       Model problems in computing

a.       Graphs

b.      trees

c.       Markov chains

XIV.       Data structures and algorithms for graphs and trees

a.       Enumeration

b.      practical instantiation

c.       Producing a random graph, tree, and table

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

The following is a part of the University's urge to measure the benefits of education. While it may well be that the most important effect of education is creativity, that effect, is, almost by definition of the term, indefinable, hence immeasurable, rending a part of this urge intrinsically quixotic.  This is taken from I:\Computer_Science\All Faculty\CourseOutcomes08\311Outcome.htm.