York UniversityMath 1019Final ExamApril 10, 2012Last Name:First Name:Student #:Question Points Marks1 102 83 124 145 86 87 108 109 109 10Notes. 1. The duration of the test is 180 minutes sharp. When the test is over, stop writinginstantly, close your test book and pass it to the person in your row sitting next to the aisle.2. Since you will have to stop writing once the test is over, write down yo
...[Show More]
York University
Math 1019
Final Exam
April 10, 2012
Last Name:
First Name:
Student #:
Question Points Marks
1 10
2 8
3 12
4 14
5 8
6 8
7 10
8 10
9 10
9 10
Notes. 1. The duration of the test is 180 minutes sharp. When the test is over, stop writing
instantly, close your test book and pass it to the person in your row sitting next to the aisle.
2. Since you will have to stop writing once the test is over, write down your name and student
number in ink (pencil is not acceptable) before you start working.
3. Answer all questions.
4. Present your solutions in a clear and well-organized manner. Show all work in all questions
unless otherwise specified. Full marks will not be given unless all work is shown in a clear and
organized manner.
5. Have a photo ID and a sessional student card on your desk ready for checkup.
1
This study source was downloaded by 100000823518935 from CourseHero.com on 04-24-2021 13:51:35 GMT -05:00
https://www.coursehero.com/file/9342446/Final-Examination/
This study resource was
shared via CourseHero.com
1. (10pts) Prove that n! is not O(2n), but 2n is O(n!).
2. (8pts) Recall that Kn is the complete graph with n vertices and that Km;n is the complete
bipartite graph whose vertex set is partitioned into two sets of cardinality m and n, respectively,
with an edge between two vertices if and only if those vertices belong to distinct parts. Fill the
table and justify your answers.
graph number of vertices number of edges
Kn
n
K
m;n m + n
2
This study source was downloaded by 100000823518935 from CourseHero.com on 04-24-2021 13:51:35 GMT -05:00
https://www.coursehero.com/file/9342446/Final-Examination/
This study resource was
shared via C
[Show Less]
-preview.jpeg)
