York UniversityMATH 1019....2020 Final Examination

Document Content and Description Below

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 t... he 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.com1. (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 More]

Last updated: 1 year ago

Preview 1 out of 7 pages