DARTMOUTH COSC 030 - 05sumproduct (6 pages)

Previewing pages 1, 2 of 6 page document View the full content.
View Full Document

05sumproduct



Previewing pages 1, 2 of actual document.

View the full content.
View Full Document
View Full Document

05sumproduct

50 views


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

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

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view 05sumproduct and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view 05sumproduct and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?