CSC 270 – Discrete Structures of Computer Science

Spring 2015

 

Instructor:     Dimitris Papamichail

Office:             Forcina Hall 458

Email:               papamicd (at tcnj)

                           (most emails are answered within 24 hours during business days)

URL:                  www.tcnj.edu/~papamicd

Office Hours:          Wednesdays 10am – 11:30am, Fridays 11am – 12:30pm, and by appointment.

Class Time:      Tuesdays/Fridays 1:30pm – 3:20pm

Class Room:    Forcina Hall, room 410

 

Course Description

Introduction to concepts and structures fundamental to computer science. Declarative programming techniques will be used to explore discrete structures. Topics include logic, relations, functions, word algebras, induction, recursion, combinatorics, finite state machines, graphs, and trees.

PREREQUISITES: Completion of CSC 215, 220, or 250 with a C or better.

COURSE UNITS: 1

 

Course Materials

Textbook: The required textbook for the course will be:

o   Discrete Mathematics and Its Applications, Kenneth H. Rosen, 7th Edition, 2012, McGraw-Hill.

 

Course Requirements

o   Attendance and readings

o   Weekly assignments

o   Midterm exam

o   Final exam

 

Course Purpose and Learning Goals

The purpose of this course is to introduce students to concepts and structures fundamental to computer science, including sets and relations, regular expressions, finite deterministic and non-deterministic automata, logic. By the end of the course students will be able to:

In this class, the deep learning outcomes associated with TCNJÕs 4th hour are accomplished by additional lecture time, during which the students are exposed to in-depth concept analysis and additional examples.

 

Course Topics and Schedule (subject to change)

Dates

Topic

Assignment

1/26

Propositional Logic, Applications

 

1/29

Propositional Equivalences, Satisfiability

Homework Assignment 1

(due on 2/5)

2/2

Predicates and Quantifiers

2/5

Nested Quantifiers

Homework Assignment 2

(due on 2/12)

2/9

Rules of Inference


2/12

Sets and Operations

Homework Assignment 3

(due on 2/19)

2/16

Functions

2/19

Divisibility and Modular Arithmetic

Homework Assignment 4

(due on 2/26)

2/23

Integer Representations and Algorithms

2/26

Mathematical Induction

Homework Assignment 5

(due on 3/5)

3/2

Recursive Definitions

3/5

Recursive Algorithms

 

3/9

Midterm

3/12

Counting.

Homework Assignment 6

(due on 3/26)

3/23

The Pigeonhole Principle.

3/26

Permutations and Combinations

Homework Assignment 7

(due on 4/2)

3/30

Relations, Properties, Applications

4/2

Representing Relations

Homework Assignment 8

(due on 4/9)

4/6

Closures

4/9

Equivalence Relations


Homework Assignment 9

(due on 4/16)

4/13

Languages and Grammars

4/16

Finite State Machines

Homework Assignment 10

(due on 4/23)

4/20

Language Recognition

4/23

Turing Machines

Homework Assignment 11

(due on 4/30)

4/26

Graphs

4/30

Representing Graphs

Homework Assignment 12

(due on 5/7)

5/4

Connectivity Trees


5/7

Tree Applications and Traversals

 

 

Grading

o   Homeworks: 40%

o   Midterm exam: 20%

o   Final: 40%

 

Course Policies

o   Most course material will be posted on canvas. Check often.

o   We will utilize piazza (www.piazza.com) for class discussions.

o   Homework must be submitted in hardcopy form, at the beginning of the class. Multiple page assignments have to be stapled together. Unstapled copies will receive a 5% penalty. Assignments missing information such as name, course number, assignment number, and date will receive a 5% penalty.

o   Homework will be assigned roughly once every week. Assignments will appear on canvas, together with instructions.

o   The lowest homework grade will be dropped.

o   No missed homework will be allowed. Since the lowest homework grade will be dropped, students may take this dropped grade as one free missed homework.

o   Late homework deliverables are accepted with penalty: 20% per day.

o   Grades can be disputed for two weeks following the return of graded work only.

o   Please be on time and prepared for class, and silence all cell phones before class starts.

Additional Information:

  1. Homework Assignments: I encourage discussion among students, but the solutions to assignment problems should be your own. Homework submissions would benefit by being typed in appropriate typesetting software, such as LaTeX or MS Word, including mathematical formulas. Computer generated figures would be desirable to explain complicated constructions. Handwritten solutions, formulas, and figures will be accepted, but points will be deducted for unreadable text, formulas, and figures.

The midterm and final exams may include problems that are similar to ones encountered in the homework assignments. Failing to solve these problems will indicate a lack of individual effort towards the homework assignments.

  1. Midterm Exam: The midterm exam will test your understanding of the material and ensure you revise the topics covered so far. The midterm exam will be closed book.
  2. Final Exam: The final exam will be comprehensive to encourage students to review all material taught. The final exam will be closed book. Solving your homework assignment problems without aid should help with constructing novel solutions on demand. Exam questions may vary from homework problems in ways that memorizing solutions may confuse you instead of helping you.
  3. I will be lecturing mostly from slides, but will use the board whenever needed for examples and other illustrations. Feel free to keep notes if you wish, but you do not have to copy the slide material, since it will be made available to you.
  4. Course handouts, material, homework assignments, etc. will be available on canvas after being presented in class, along with the latest announcements. Please check them out often. Also, please setup canvas appropriately to receive email notifications when announcements are made.
  5. Solutions to problems should be precise and concise. I may be placing space restrictions for problem solutions, which may save you the ordeal of trying to impress me with volume instead of quality.
  6. The best way to learn the material is by solving problems. Unless you learn how to solve problems, I can promise that you will get burned on the exams and thus for your final grade.
  7. Because a primary goal of the course is to teach professionalism, any academic dishonesty will be viewed as evidence that this goal has not been achieved, and will be ground for receiving a failing grade. Please review the TCNJ academic integrity policy (link below).
  8. This is the second time I am teaching this course, but I still expect numerous changes/adjustments to the material, homework assignments, and exams. I am open to suggestions to improve and direct the subjects covered, although I have an obligation to cover certain material.
  9. The required textbook will be followed to a great extent, but we may deviate in several subjects, as well as bypass and/or add material. It is recommended that you study the relevant sections from the book, which provides additional examples and explanations. Any additional slides will be made available on canvas.

 

Selected TCNJ Policies

TCNJÕs final examination policy is available on the web: http://policies.tcnj.edu/policies/digest.php?docId=9136

Attendance

Students are expected to be present, on time, and prepared to participate in each scheduled class session as detailed in TCNJÕs attendance policy, available on the web at: http://policies.tcnj.edu/policies/digest.php?docId=9134

Academic Integrity Policy

The Academic Integrity Policy of TCNJ, available on the web at: http://policies.tcnj.edu/policies/digest.php?docId=7642

Americans with Disabilities Act (ADA) Policy

Any student who has a documented disability and is in need of academic accommodations should notify the professor of this course and contact the Office of Differing Abilities Services (609-771-2571). Accommodations are individualized and in accordance with Section 504 of the Rehabilitation Act of 1973 and the Americans with Disabilities Act of 1992.

TCNJÕs Americans with Disabilities Act (ADA) policy is available on the web:

http://policies.tcnj.edu/policies/digest.php?docId=8082