Discrete Structures - Spring, 2017
Instructor: Geoff Hagopian,
office: Math 12, MW: 12:45-2, TR: 9:20-10
Description: A study in discrete mathematical systems for computer science including methods of proof that shape the foundations of computer science. Includes propositional logic, set and number theory, Boolean Algebra, deductive and inductive proof, functions and relations, combinatorics, discrete probability, graph theory and network models, and efficiency of algorithms.
2. Analyze the relationships among counting techniques (combinatorics), discrete probability, sets, Boolean algebra, propositional logic, and the construction of digital circuits.
3. Evaluate graphs, trees, and networks in terms of efficiency, redundancy, and similiarity.
4. Evaluate and prove the efficiency of computer algorithms.
Course Objectives: Upon completion of this course, students will be able to:
1. Apply the principles of mathematical induction, direct and indirect deductive methods of proof to explore integers, rationals, and reals, and their relationships (number theory).
2. Provide recursive, iterative and explicit solutions to classic discrete mathematical problems.
3. Illustrate functional similarities of set theory, discrete probability, propositional logic, Boolean algebra, and digital circuits.
4. Apply graph theory and principles of combinatorial analysis to network models.
5. Create and manipulate trees and specifically spanning trees to find their minimized forms.
6. Create and search Eulerian and Hamiltonian graphs.
7. Identify and solve discrete probability and combinatorial problems.
8. Identify and solve recurrence relations including equivalence relations and partial orderings.
9. Compare the efficiency of common sorting and searching algorithms in terms of
big-O, big-Omega, and big-Theta notation.
10. Convert mathematical algorithms into computer programs.
Textbook: Essentials of Discrete Mathematics: by David J. Hunter ISBN-13: 9781284056242
Weekly assigned reading and exercises are designed to engage your open mind and develop your understanding of course topics. Students would do well to follow this guide:
(1) Begin at the beginning, and do not allow yourself to dive into the middle of a difficult topic, only to abandon it because it's "too hard," and thus losing the chance of adding a very large item to your stock of mental delights.
(2) Don't satisfy yourself with a shallow, superficial acquaintance with a topic - instead, seek a thorough understanding and make sure you have correctly worked the examples which have been set.
(3) If you come by some reading you don't understand, read it again. If you don't understand it after a second reading, read it a third time. If you still don't understand it, very likely your brain is getting a little tired. Put the book away for a while and then come back to it when you are rested. You may find it quite easy to understand then.
(4) If possible, find some genial friend who will read the book along with you, and will talk over the difficulties with you. Talking is a wonderful smoother-over of difficulties.
· In-class Activities: These will include "warm-ups", where, typically at the start of a class, students will present their homework to the class. It may include on-line or pencil/paper assignments designed to help you get acquainted with the vocabulary and theories of discrete structures. During lab time we will play games,
goof around, design and implement algorithms and experiment with software...in particular, Jupyter Notebooks and Python code.
· Project: Each student will complete a project involving a more in-depth study of some application of discrete structures
· Exams: There will be midterm in-class exams and a final in-class exam.
Grading: Warmups: 5%, Homework: 50%, Project 10%, Exams: 35% (20% midterms, 15% final)