CSE 260 Fall 2005

Mathematical Foundations of Computer Science

Solutions of Take Home Final are Available

Instructor:

Jean Gallier:
- Office: CIS Department, 476 Levine GRW
- Office Hours: Tu 4:45-6:00pm, Th 4:45-6:00pm
- Phone: 898-4405
- E-mail: jean@saul.cis.upenn.edu
- Home Page: http://www.cis.upenn.edu/~jean

CSE 260 Newsgroup
- All announcements concerning review sessions or homework will be posted on the course newsgroup. Please check the newsgroup for updates.
- upenn.cis.cse260

Teaching Assistants:

Name:	E-Mail:	Office Hour Time:	Office Hour Location:
Ryan Gabbard	ryang@audhumla.org	Wed. 2:00-3:00pm	Contact Ryan! (Levine 575)
Ken Zhu	qihuizhu@seas.upenn.edu	Mon. 4:45-6:00pm	Conference Room outside GRASP Lab (Levine 402)
Usman Hassan	usman@seas.upenn.edu	Fri. 10:00-11:00am	Levine Cafe'

You may email any TA with questions about the course material.
You can meet with any TA to set up a meeting for extra help.

Class Schedule:

Lectures: Tuesday, Thursday 10:30-11:50, Towne 311

Recitations: Friday 14:00-14:50, Heilmeier

Names:	Location:	TA:
??	??	X
??	??	Y
??	??	Y

Midterm Examination Schedule:

Midterm I: Friday 7 October, 2:00-2:50pm; Room: Heilmeier
Review Problems (ps) (pdf)
Solutions to review problems (pdf)
Midterm Solutions (pdf)

Midterm II: Friday 11 November , 2:00-2:50pm; Room: Heilmeier
Review Problems (ps) (pdf)
Solutions to review problems (pdf)
Midterm Solutions (pdf)

Take home Final: Due by Wed. 14 December , 11am;
Final (ps) (pdf)
Solutions to Final (pdf)

NB: Makeup midterm examinations will only be given for verified medical reasons. All makeup examinations are oral.

Weekly Quizzes:

There will be 4 written quizzes lasting 15-20 minutes. The quizzes will be scheduled on Fridays in those weeks when there is no preliminary examination scheduled. The purpose of the quizzes is to aid students in keeping current on the homework and lecture material. The subject material of the quizzes will be taken from the homework assignments and lectures. The tentative quiz schedule is: September 16, 30; October 14, 28 No makeup quizzes will be given.

Quiz 1 (pdf)
Solutions for Quiz 1 (pdf)
Quiz 2 (pdf)
Solutions for Quiz 2 (pdf)
Quiz 3 (pdf)
Solutions for Quiz 3 (pdf)
Quiz 4 (pdf)
Solutions for Quiz 4 (pdf)

Homeworks:

Homework 1 (ps) (pdf) (latex)	Solution (ps) (pdf) (latex)
Homework 2 (ps) (pdf) (latex)	Solution (ps) (pdf) (latex)
Homework 3 (ps) (pdf) (latex)	Solution (ps) (pdf) (latex)
Homework 4 (ps) (pdf) (latex)	Solution (ps) (pdf) (latex)
Homework 5 (ps) (pdf) (latex)	Solution (ps) (pdf) (latex)

Examination Policy:

NB: All midterm examinations and quizzes are closed-book examinations. No written notes, personal assistants, or calculators are permitted.

Written Assignments Policy:

Written assignments (problem sets) will be given weekly during lecture and recitation. The problems will vary in difficulty and will be designed to reinforce and augment the material in the lectures and texts.

Assignments include: analytical work, derivations, proofs, and algorithms.

The assignments will be collected and graded. Each assignment must be submitted at the beginning of the class in which it is due. Late submissions will not be accepted. Our goal is to grade all of the homework that is submitted in a timely fashion. However, due to the size of the class, it may become necessary from time to time to limit grading to a selected subset of the assigned problems. For example, if five problems are assigned in a given set, we might select three of the five problems for grading.

Problem set solutions will be discussed in the recitation section with additional commentary from time to time in the lectures. Solutions to the homework problems will be distributed in class.

You are permitted to discuss the homework problems with other class members with the following limitations. These discussions are to be limited to high-level concepts. You are not permitted to copy or share written work or implementation details. It is understood that the work that you submit may be based on these discussions but has not been either copied directly from another student's paper nor is it, in part or in whole, the product of impermissible collaboration.

All written work must be neat, well-organized, and include sufficient explanations in the delineation of the solutions. Messy, poorly organized, or illegible material will be returned ungraded.

Each homework set will be graded based on the following grade levels: E (excellent), G (good), S (satisfactory), U (unsatisfactory), NC (no credit).

Grading Policy:

The final course grade : TBA

Policy on Grade Scaling: The instructor retains the option to scale the exam grades. Historically, we have: (1) dropped the lowest quiz grade; (2) adjusted the median of a preliminary exam to 75, when the raw median was below 75; (3) adjusted the median of each part of the final exam to 75, when the raw median was below 75; and (4) dropped the lowest of the four scores: Mid I, Mid II, Final part I, and Final part II.

Regrades: Regrades for exams and quizzes will not be done in person. You must fill out the regrade form (download here) and hand it to any TA. We will not accept regrades for homework.

Recommended Text:

Mathematics -- A Discrete Introduction: Edward R. Scheinerman

Also of interest:

Mathematical Thinking --- Problem-Solving and Proofs: John D'Angelo and Douglas West, Prentice Hall

The MacTutor History of Mathematics archive

Welcome Page

The Mathematics Genealogy Project

Home Page

CSE 260 Course Topics:

Mathematical reasoning and proof principles, Logic

Set Theory

Relations, Functions, Partial Functions

Induction on N

Composition of relations and functions

Recursion on N

Injection, surjections, bijections

Inverses of functions and relations

Direct and Inverse Images

Equinumerosity, Cantor's Theorem,

Pigeonhole Principle, Schroeder-Bernstein's Theorem

Strings, Multisets, Indexed Families

An amazing surjection: Hilbert's square-filling curve

Some counting problems

Binomial coefficients, the binomial formula

Partial Orders, Lattices

Well-Founded Orderings and complete Induction

Equivalence Relations and Partitions. Closures.

Distributive Lattices, Boolean algebras, Heyting algebras

Trees, Multiset Ordering, String and Tree Embedding

Graphs (directed and undirected; unlabeled and labeled); Graph homomorphisms and isomorphisms

Simple Combinatorics--Counting

Baby Number Theory: divisibility, modular arithmetic

Probability

The required reading will be posted each week.

Related Material: Some Talks, Slides and Links

Intuitionistic logic for dummies (pdf)
Intuitionistic logic (Part 2/2) (pdf)
Introduction to proof theory (pdf)
Proofs are programs (ppt)
Intuitionistic Logic (from Stanford Encyclopedia of Philosophy) (html)
Intuitionistic Logic (From Wikipedia) (html)
Intuitionistic Logic (From Mathworld) (html)
Intuitionistic Logic (From Absolute Astronomy) (html)
Axioms of Zermelo-Fraenkel Set Theory (from Wikipedia) (html)
Zermelo-Fraenkel Axioms (from MathWorld) (html)
Zermelo-Fraenkel Set Theory (from Stanford Encyclopedia of Philosophy) (html)
Set Theory (from Stanford Encyclopedia of Philosophy) (html)
The Axiom of Choice (by Eric Schechter) (html)
Eric Schechter's home page (html)
Axiom of choice (from Wikipedia) (html)
Axiom of choice (from MathWorld) (html)
Cantor-Schroeder-Bernstein Theorem (from Wikipedia) (html)
Cantor-Schroeder-Bernstein Theorem (from PlanetMath) (html)
Tarski's Fixed Point Theorem (from MathWorld) (html)
Knaster-Tarski Theorem (from Wikipedia) (html)
Plane-Filling Function (from MathWorld) (html)
Hilbert Curve (from MathWorld) (html)
Plane Filling Curves (from Alexander Bogomolny) (html)
Space-Filling Curves (from Wikipedia) (html)
Using Space-Filling Curves for multi-dimensional indexing (html)
Stirling's Formula (from Wikipedia) (html)
Well-founded relation (from Wikipedia) (html)
Well-founded induction (from PlanetMath) (html)
Lattice (from Wikipedia) (html)
Distributive Lattice (from Wikipedia) (html)
Complete Lattice (from Wikipedia) (html)
Boolean algebra (from Wikipedia) (html)
Boolean algebra (from Stanford Encyclopedia of Philosophy) (html)
Graph theory (from Wikipedia) (html)

Some Course Notes and Slides

Discrete math. basics, induction, inductive definitions
(Chapter from ``Logic for Computer Science'', by J. Gallier) (ps) | (pdf)
Macro prooftree.tex (tex)
Macro mac.tex (tex)
Macro mathmac.tex (tex)
Discrete Mathematics for Computer Science (book manuscript) (html)

** Solutions of Take Home Final are Available **

Quiz 1 (pdf) Solutions for Quiz 1 (pdf) Quiz 2 (pdf) Solutions for Quiz 2 (pdf) Quiz 3 (pdf) Solutions for Quiz 3 (pdf) Quiz 4 (pdf) Solutions for Quiz 4 (pdf)