CS 222: Computer Science II

Fall 2003

Date	Lecture Topic	Reading	Graded Events
09/02 09/04	Logic Equivalences, Tree ADT	DM 1.1 DM 1.2, DSA 6.1
09/09 09/11	Predicates and Quantifiers Nested Quantifiers, Tree Algorithms	DM 1.3 DM 1.4, DSA 6.2
09/16 09/18	Proof Methods Sets, Binary Trees	DM 1.5 DM 1.6, DSA 6.3
09/23 09/25	Set Operations, Tree Data Structures Functions	DM 1.7, DSA 6.4 DM 1.8
09/30 10/02	Binary Search Trees Tree Applications, AVL Trees	DM 9.1, DSA 9.1 DM 9.2, DSA 9.2
10/07 10/09	Tree Traversal, Multi-Way Trees Spanning Trees, (2,4) Trees	DM 9.3, DSA 9.3 DM 9.4, DSA 9.4
10/14 10/16	MSTs and Red-Black Trees Counting Basics	DM 9.5, DSA 9.5 DM 4.1
10/21 10/23	Pigeonhole Principle Permutations, Combinations	DM 4.2 DM 4.3-4.4
10/28 10/30	Review Exam		Exam (15%)
11/04 11/06	Generalized Permutations Generating Permutations, Heaps	DM 4.5 DM 4.6, DSA 7.3
11/11 11/13	Veteran's Day - No Classes! Discrete Probability	DM 5.1
11/18 11/20	Probability Theory Expected Value and Variance	DM 5.2 DM 5.3
11/25 11/27	Boolean Functions, Social Issues Thanksgiving - No Class!	DM 10.1
12/02 12/04	Representing Boolean Functions Logic Gates, Social Issues	DM 10.2 DM 10.3
12/09 12/11	Circuit Minimization Review	DM 10.4
12/15	Final, noon - 1:50 p.m.		Final (30%)

Grading

45% of your grade comes from exams. 55% of your grade comes from the laboratory. To pass the course, you must average at least 50% on the exams. The final will not be given early.

Meeting Times

Lecture: Tuesday, Thursday 12:45 p.m. - 2:00 p.m. in EPS 103.
Laboratory: Wednesday 8:00 a.m. - 9:50 a.m. (section 2), 10:00 a.m. - 11:50 a.m. (section 3), or noon - 2:00 p.m. (section 4) in EPS 110.

Textbooks

Discrete Mathematics and its Applications, 5th Edition, by Rosen.
Data Structures and Algorithms in Java, 2nd Edition, by Goodrich & Tamassia.

Instructor

John Paxton. EPS 363. 994-5979. Office Hours: Tuesday 2:10-4:00, Thursday 2:10-4:00.

Course Outcomes

At the end of the course, students should be able to

Understand the binary search tree ADT and be able to implement it.
Understand balanced binary search trees.
Understand applications of trees.
Understand the heap implementation of the priority queue ADT
Understand a couple of specific social issues relating to computers and society.
Solve problems that use logic, sets, and functions.
Solve problems that use permutations and combinations.
Solve problems that use discrete probability.
Solve problems using Boolean Algebra.

Other Information

Last modified: December 14, 2003.