Homework 1
(Maximum 50 points)
Due 11:59 pm Friday September 11, 2020
Show the steps of deriving your answers. Points will be deducted for answers without adequate steps discussed. Submit your homework via Blackboard as one PDF or Word document.
1. (25) [Asymptotic upper bound] Prove or disprove each of the following two claims: 2n+1 = O(2n) and 22n = O(2n). Use the formal definition of asymptotic upper bounds (big-O, see p36 of the textbook) to prove or disprove it. To prove it, it suffices to provide an evidence (e.g., values of the two constants c and n0). To disprove it, show why such an evidence cannot exist.
2. (25) [Adjacency matrix and adjacency list] Consider the directed graph shown below.
(a) Show an adjacency matrix representation and an adjacency list representation of the graph. A node is not adjacent to itself unless there is a self-loop.
(b) For each graph representation, write pseudocode of algorithm Find_all_edges that outputs all edges in the graph, and show its big-O run-time complexity – make sure to show the steps of deriving the run-time complexity; no point will be given to an answer without the steps.
Last modified: September 7, 2020