CSCI 2011: Discrete Structures of Computer Science

Overall Description

2011 is a required undergraduate course that we expect students to take in their sophomore year. It is a required class for both computer science and computer engineering majors. It is also one of the courses required for admission to the CSci major, and is a prerequisite for many of the higher level CSci classes. 2011 focuses on fundamental structures (e.g., sets, trees), techniques for solving discrete structures problems, and rigorous analysis and proofs. Upon successfully completing this class, students should be able to use these structures and techniques in analyzing and solving a variety of problems, and be able to present their analysis/solution in a clear, concise, accurate manner.

Catalog Description

Foundations of discrete mathematics including sets, sequences, functions, big-O, propositional and predicate logic, proof methods, counting methods, recursion and recurrences, relations, and trees and graph fundamentals.

Content

Week 1-2: FOUNDATIONS: sets, sequences and summations; functions and their growth rate (big-O notation); applications of big-O to algorithm analysis; propositional and predicate logic. Introduction to proofs.
Week 3-4: NUMBER THEORY: basics and applications.
Week 5-6: PROOF METHODS: direct proof, indirect proof, proof by contradiction, proof by cases, and generalization; illustration of these via concrete (as opposed to WFF-based) examples.
Week 7: MATH INDUCTION: illustration of first and second principle with multiple bases and multiple variables; justification of induction as a valid method; elements of program correctness, relation to other proof methods.
Week 8-9: RECURSION AND RECURRENCES: recursive definitions and recurrences modeling counting problems with recurrences; solution of linear recurrences; recursive algorithms and their analysis via recurrences (e.g., divide-and-conquer).
Week 10-11: COUNTING METHODS: basics; pigeonhole principle and applications; permutations and combinations; inclusion-exclusion principle; applications to problems from various domains.
Week 12-13 RELATIONS: properties of relations; representation; closure of relations and their computation (Floyd-Warshall algorithm); equivalence relations; partial orderings and their applications (e.g., topological sort).
Week 14-15: TREES AND GRAPHS: introduction, terminology, applications; tree traversals; minimum spanning trees; connectivity and tours of graphs; shortest path problems; graph coloring; planar graphs; graphs isomorphism.

Two other topics that could be included, at the expense of some other topics, are:

  • Discrete Probability (1 week)
  • Boolean Algebra (1 week)

Why This Class is Important and its Role in the Curriculum

Much of computer science assumes familiarity and skill with the fundamental structures, concepts, proof techniques, and problem solving techniques in this class. Moreover, many employers say that logical analysis and problem solving skills, which are one concern of this class, are essential skills in employees.

Most students will take 2011 in their second year. It is one of the courses required for admittance to the CSci major. Transfer students who have completed 2 years at another school should have taken an equivalent class.

Prerequisites and Rationale

Calculus I. 2011 uses proof techniques and mathematical or logical analysis heavily. Although a portion of the class is devoted to exposing students to different proof techniques, and to having them practice their analysis skills on discrete structures, we assume that students have already had some exposure to mathematical reasoning. Moreover, although the explicit concern of Calculus I is differential and integral calculus, an implicit concern is developing students' mathematical reasoning skills, and for this reason it is a suitable prerequisite for 2011. In general, the students who have the most difficult time in 2011 are those who struggle with the reasoning skills needed for the class.

Classes Having 2011 as a Prerequisite and Rationale

These include 4011 (Automata), and 4041 (Algorithms), which in turn are prerequisites for many elective classes. 2011 is also a direct prerequisite for 5511 (Artificial Intelligence) and 5801 (Software Engineering I). 2011 teaches many of the fundamental skills (logical reasoning, proof techniques, counting methods) and structures (trees, graphs, relations) used extensively in the rest of Computer Science. To give a couple quick examples, (i) proof techniques are used to in 4041 to prove algorithm correctness, or to prove results about algorithms (such as time bounds); (ii) trees are used extensively, for example in graphics and computer aided design, to model objects using constructive solid geometry.

Class Format

4 credits, 3 hours large class + 1 recitation hour per week. Recitation can be used for problem solving and review, or more in-depth discussion of topics and examples given in the large class. Since one of the emphases of the class is on developing students' problem solving skill, the practice given in recitation will be highly valuable for many students.

Probable Text, If Any

Discrete Mathematics and its Applications, K.H. Rosen, McGraw-Hill. (Possible supplemental text: Applications of Discrete Mathematics, Michaels and Rosen).

Outcomes

Upon successful completion of the course students should have the following skills and proficiencies:

  1. For each of the structures (e.g., graphs) or techniques (e.g., counting methods, proof techniques) discussed in class, the student should be able to
    1. define the basic terminology and use it correctly,
    2. give an explanation of why it is important,
    3. provide and discuss specific CSci examples of its use,
    4. be able to identify its important characteristics, as well as any variants or special cases,
    5. perform the basic operations associated with it,
    6. use it, when applicable, to analyze and solve problems.
  2. Students should also have the following additional analysis, problem solving, and presentation skills. Given a problem, students should be able to:
    1. identify which structures and/or techniques could be useful in analyzing or solving the problem, and why,
    2. modify or specialize structures or techniques to make them applicable to problems that are not amenable to straightforward use of the structure or technique,
    3. present a clear, concise, logically accurate, and rigorous solution,
    4. tell whether a purported solution or analysis is accurate;
    5. given a problem whose solution requires a rigorous proof, be able to both choose an appropriate type of proof (e.g., induction), and be able to construct a rigorous and well-written proof.