-
Department Info
-
-
Admissions
-
-
Academics
-
-
-
Research
-
-
-
Main navigation | Main content
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), 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.
Foundations of discrete mathematics including sets, sequences, functions, big-O, propositional and predicate logic, proof methods, counting methods, recursion and recurrences, relations. Regular Languages and finite state machines.
| Week 1-3: | FOUNDATIONS: logic, proofs and sets. Propositional Logic, Predicates and Quantifiers. Proofs. Rules of inference. Proof methods. Sets, sequences and summations. 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 4-5: | ALGORITHMS AND THEIR ANALYSIS: algorithms; growth rate of functions, big-O notation. applications of big-O to algorithm analysis. Algorithm complexity. |
| Week 6: | NUMBER THEORY: integers and division, prime numbers and greatest common divisors. Algorithms on integers. |
| 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; analysis of recursive algorithms 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: | MODELLING COMPUTATION: languages and grammars. Finite state machines with and without output. Recognizing languages and regular expressions. |
Three other topics that could be included, at the expense of some other topics, are:
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.
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.
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 ( 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) finite state machines are used extensively in algorithm design.
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.
Discrete Mathematics and its Applications, K.H. Rosen, McGraw-Hill. (Possible supplemental text: Applications of Discrete Mathematics, Michaels and Rosen).
Upon successful completion of the course students should have the following skills and proficiencies:
