# DARTMOUTH COSC 030 - 05sumproduct (6 pages)

Previewing pages*1, 2*of 6 page document

**View the full content.**## 05sumproduct

Previewing pages *1, 2*
of
actual document.

**View the full content.**View Full Document

## 05sumproduct

0 0 50 views

- Pages:
- 6
- School:
- Dartmouth College
- Course:
- Cosc 030 - Discrete Math Computer Sci

**Unformatted text preview: **

Counting Problems CS 30 Discrete Mathematics Amit Chakrabarti Basic Counting Principles Sum Principle Basic sum principle If A and B are disjoint A B A B Extended sum principle If A1 A2 Ak are pairwise disjoint A1 A2 Ak A1 A2 Ak How many people are signed up on this course s canvas page Students Staff Students 37 Staff 7 Answer 37 7 44 Extended Sum Principle Application Exchange sort algorithm pseudocode for i 1 to n 1 for j i 1 to n if A i A j exchange A i and A j How fast is this How many comparisons SimpliRication record comparison A i A j as pair i j Extended Sum Principle Application How many pairs i j occur below for i 1 to n 1 for j i 1 to n S1 1 2 1 3 1 4 1 n S2 2 3 2 4 2 n Sn 1 n 1 n S1 n 1 S2 n 2 Sn 1 1 Total S1 S2 Sn 1 n 1 n 2 1 n n 1 2 Sum Principle Basic sum principle If A and B are disjoint A B A B Extended sum principle If A1 A2 Ak are pairwise disjoint A1 A2 Ak A1 A2 Ak Generalized sum principle For all A and B A B A B A B General Non Disjoint Unions S set of all current Dartmouth students A s S s has registered for CS 30 B s S s has registered for CS 75 C s S s registered for CS 30 or CS 75 A 37 B 25 C A B 37 25 What if I told you A B 3 Another Counting Problem Dartmouth invited to send a delegation of one student and one professor to the International Awesomeness Convention How many ways to choose Students Professors Students 4500 Professors 650 Product Principle Basic product principle For all A and B A B A B Extended product principle For all A1 A2 Ak A1 A2 Ak A1 A2 Ak Counting Telephone Numbers Rules Let X denote a digit from 0 through 9 Let N denote a digit from 2 through 9 Let Y denote a digit that is 0 or 1 In the old plan in use in the 1960s the format was NYX NNX XXXX In the new plan the format is NXX NXX XXXX Solution Use the product principle There are 8 2 10 160 area codes with the format NYX 8 10 10 800 area codes with the format NXX 8 8 10 640 ofRice codes with the format NNX 10 10 10 10 10 000 station codes with the format XXXX Old

View Full Document