CIT 592 – Mathematical Foundations of Computer Science

University of Pennsylvania

Fall 2009

Instructor: Donna Dietz

Office: Levine (GRW) 572

Phone: (215) 746-4223

Email: dietzd@seas.upenn.edu

Lecture: TR 1:30-3:00 Towne 313

Recitation: (Jack Sim - TA) F 1:00-2:30 Moore 212

Office Hours: TR 3:00-4:00, W 11:00-noon







Text: Discrete Mathematics and Its Applications, Kenneth H. Rosen, 6th edition


Official Course Description: L/R 592. Mathematical Foundations of Computer Science. (C) Foundations: Sets, Functions, Summations, and Sequences. Introduction to algorithms. Counting techniques: The pigeonhole principle, permutations and combinations. Discrete probability. Selected topics from Number theory and/or Graph theory.


L/R means Lecture/Recitation, registration in both is required.

(C) indicates the course may be offered either in the Fall or the Spring for one term.

Welcome to the MCIT program at the University of Pennsylvania!

Upcoming event:

Thursday September 17, 6-8 pm Levine 307

Social event for MCIT students

(Pizza will be served.)


This course is part of a two-course sequence in the MCIT program. (CIT596, Theory of Computation, is the other course in this sequence.) This program is intended to prepare students to begin or further their careers in Information Technology. Students were accepted into this program, not for their background (which is typically not computer science or even a closely related field), but because of their solid academic backgrounds which indicate a demonstrated ability to master new skills and accept academic challenges. Students beginning this program are not expected to have any specific background (other than basic algebra), but are expected to have a graduate level academic maturity in terms of study skills, motivation, and the ability to work hard.


Grading: Your final grade for the semester will be weighted as follows: 25% each for Exam I and Exam II, 30% for the Final, and 20% for the various homeworks and projects which will be assigned roughly once per week during the semester. All assignments and other announcements will be posted through Blackboard. Initial assignments will not require programming, but after Exam I, concepts covered in CIT 591 will be integrated into the course homeworks/projects.








Calendar:

This course meets 26 times for 90 minutes during the semester, plus once (2 hours) for the final exam.

date

agenda

chapter titles

1

Th Sept 10

Intro, 1.1

Propositional Logic

2

Tu Sept 15

1.2-1.5

Propositional Equivalences, Predicates, Quantifiers, Nested Quantifiers, Rules of Inference

3

Th Sept 17

1.6-1.7,2.1

Intro to Proofs, Proof Methods/Strategies, Sets

4

Tu Sept 22

2.2,3.1-3.2

Set Operations, Algorithms, Growth of Functions

5

Th Sept 24

3.3-3.4

Complexity of Algorithms, Integers and Division

6

Tu Sept 29

3.5-3.6

Primes and GCDs, Integers and Algorithms

7

Th Oct 1

3.7

Applications of Number Theory (RSA)

8

Tu Oct 6

3.8,4.1

Matrices, Mathematical Induction

9

Th Oct 8

Exam I

(on material from days 1-7)

10

Tu Oct 13

4.3-4.4,5.3

Recursive Definitions and Structural Induction, Recursive Algorithms, Permutations and Combinations

11

Th Oct 15

5.4-5.5

Binomial Coefficients, Generalized Permutations and Combinations

12

Tu Oct 20

6.1-6.2

Intro to Discrete Probability, Probability Theory

13

Th Oct 22

7.1-7.2

Recurrence Relations, Solving Linear Recurrence Relations

14

Tu Oct 27

8.1,8.3

Relations and Their Properties, Representing Relations

15

Th Oct 29

8.6,9.1-9.2

Partial Orderings, Graphs and Graph Models, Graph Terminology and Special Types of Graphs

16

Tu Nov 3

9.3-9.4

Representing Graphs and Graph Isomorphism, Connectivity

17

Th Nov 5

Exam II

(on material from days 8 and 10-15)

18

Tu Nov 10

9.5,9.7

Euler and Hamilton Paths, Planar Graphs

19

Th Nov 12

9.8

Graph Coloring

20

Tu Nov 17

10.1

Intro to Trees

21

Th Nov 19

10.2-10.3

Applications of Trees, Tree Traversal

22

Tu Nov 24

10.4-10.5

Spanning Trees, Minimal Spanning Trees

23

Tu Dec 1

11.1-11.2

Boolean Functions, Representing Boolean Functions

24

Th Dec 3

11.3-11.4

Logic Gates, Minimization of Circuits

25

Tu Dec 8

LAB DAY

Logic Lab

26

Th Dec 10

Review



Mo Dec 21

9am-11am

FINAL EXAM

(cumulative, but double weight on material from days 16 forward)









This is a non-exhaustive list of problems the students will be expected to master. Additional problems may be assigned in class and/or recitation.

section

page

problems

1.1

16

1-13 odd,23, 27-38 odd, 36, 45, 46

1.2

28

1, 5, 9

1.5

72

3,5,7,13

1.6

85

3,6,17,25

2.1

119

1,4,5,17

2.2

130

1,3,4,25-31,35,36, 50, 51, 55

3.1

177

3,11,16,35,41

3.2

191

1-9 odd, 15,19,21,22,28a

3.3

199

1,5,7

3.4

208

17, 19

3.5

217

4-6, 20

3.6

229

1-12, 23,24

3.7

244

3,5,7,11,29,46,47

3.8

254

1-5,10,11,18-20

4.1

279

3-9,15,19,33

4.3

308

1,7,9,18

4.4

321

50,51

5.3

360

1-6,15-17,19-20,25,31,33

5.4

369

2,6

5.5

379

1,3,9,11,13,19

6.1

398

1-15 odd

6.2

414

1-5,11-28odd

7.1

456

1,5,9,25

7.2

471

1,3,5,13,24,25,28,32

8.1

527

1-31 odd, 54

8.3

542

1-28

8.6

578

5-11,25-27,32,33,43

9.1

595

2-9,21

9.2

608

1,3,4,5,7-10,20-25,37

9.3

618

5,11,25,35,39

9.4

629

1,5,37

9.7

665

3,5,7,13,20

9.8

672

1-9 odd, 19, 24

10.1

693

1-3,17,19,21,22,33

10.2

708

1-5,9

10.3

722

1-7,10,13,16-19

10.4

734

1-10

10.5

742

5-8

11.1

756

1-6,25,27,33

11.2

760

1-9 odd, 10, 11

11.3

765

1-11 odd

11.4

779

1-7 odd