Algo Hw 01 - Algo Hw 1 PDF

Preview

Summary

Algo Hw 1...

Description

ALGO Spring 2019

Section 07

HW01 solution

Problem 1: Consider the following pseudocode of a function which takes an integer n ≥ 0 as input: Function f oo(n) if n == 0 then Return; end for i = 0 to n − 1 do Print ’*’ end f oo(n − 1) Let T(n) be the number of times the above function prints a star (*) when called with input n ≥ 0. What is T(n) exactly, in terms of only n (and not values like T(n - 1) or T(n - 2))? Prove your statement.

When the algorithm is ran: T(0) = 0 T(1) = 1 + 0 = 1 T(2) = 2 + 1 + 0 = 3 T(3) = 3 + 2 + 1 + 0 = 6 T(4) = 4 + 3 + 2 + 1 + 0 = 10 T(5) = 5 + 4 + 3 + 2 + 1 + 0 = 15 T(6) = 6 + 5 + 4 + 3 + 2 + 1 + 0 = 21 The algorithm runs the number inputted and outputs that given number of stars. Then it decreases the value by one integer and outputs the decreased number of stars. It performs the same operation until the number reaches zero. The number of stars outputted is a summation of the number inputted into the algorithm. T (n) =

n X i=0

T (0) =

0 X

0 0(0 + 1) = =0 2 2

i=

1(1 + 1) 2 = =1 2 2

i=

2(2 + 1) 6 = =3 2 2

i=

12 3(3 + 1) = =6 2 2

1 X i=0

T (2) =

2 X i=0

T (3) =

3 X i=0

n(n + 1) 2

i=

i=0

T (1) =

i=

Page 1

ALGO Spring 2019

Section 07

HW01 solution

Problem 2: Consider the following pseudocode of a function which takes an integer n 0 as input: Function bar(n) Print ’*’; if n == 0 then Return; end for i = 0 to n − 1 do bar(i); end Let T(n) be the number of times the above function prints a star (*) when called with input n ≥ 0. What is T(n) exactly, in terms of only n (and not values like T(n - 1) or T(n - 2))? Prove your statement.

When the algorithm is ran: T(0) = 1 T(1) = 2 T(2) = 4 T(3) = 8 T(4) = 16 The number of stars in the output is two raised to the number inputted into the algorithm. T (n) = 2n

T (0) = 20 = 1

T (0) = 21 = 2

T (0) = 22 = 4

T (0) = 23 = 8

T (0) = 24 = 16

This is proven through simple induction: Basis Step: When ran through the algorithm, T(0) = 1, and T(0) = 20 = 1 Inductive Step: bar(i) = 1 + bar(0) + ... + bar(i - 1) bar(i + 1) = 1 + bar(0) + ... + bar(i - 1) + bar(i) Inductive Hypothesis: bar(i + 1) = bar(i) + bar(i) = 2bar(i) Since bar(i+1) is two times bar(i), the next number in the algorithm will output double the number of stars than the previous number.

Page 2

ALGO Spring 2019

Section 07

HW01 solution

Problem 3: You are given two connected undirected graphs, G1 = (V1, E1) and G2 = (V2, E2), with V1 V2 = , as well as a node s V1 and a node t V2. You are also given a set of edges E0 which you are able to build: each edge in E0 has one endpoint in V1 and one endpoint in V2. Thus, building any edge of E0 would connect the two graphs together, and in particular would form paths connecting s and t. You are asked to determine an edge e E0 whose addition to the graphs G1 and G2 would result in the shortest possible (i.e., smallest number of edges) distance between s and t among all the edges in E0. Give a linear-time algorithm to solve this problem. Just give the algorithm, no proofs are necessary. Recall that linear-time means linear in the size of the input, which for this case is the number of nodes plus the number of edges in the graphs G1 and G2, plus the number of edges in E0 . Hint: you can use BFS as a subroutine to solve this.

Goal: Find the edge in E0 that forms the shortest path from s to t. Algorithm: Perform a BFS from s and label each node with its distance from s. Perform the same process with t. Then go through the set of edges and for each edge, add up the distance each endpoint is from s or t. Return the edge labeled with the smallest distance.

Page 3

ALGO Spring 2019

Section 07

HW01 solution

Problem 4: DPV Problem 3.7 a.) Give a linear-time (O(n) time) algorithm to determine whether an undirected graph is bipartite.

Goal: Determine if the graph is Bipartite. Algorithm: Perform a BFS, and label the nodes distance modulo 2. With every node that is labeled, check the surrounding nodes to make sure they are the either the opposite nodes or unlabeled. If it runs through every point without conflict, it is Bipartite and return True. Otherwise it is not and return False. This algorithm works because in a bipartite graph, neighboring nodes of a node of a certain color should not be that same color. Modulo 2 of the distance would give me the only two values, 0 or 1, which represents the two colors. Therefore, as long as the ’colors’ are alternative at every distance, the graph is bipartite.

Page 4

ALGO Spring 2019

Section 07

HW01 solution

Problem 5: DPV Problem 3.11) Design a linear-time algorithm which, given an undirected graph G and a particular edge e in it, determines whether G has a cycle containing e. Goal: Determine if the given edge is in a cycle in the given graph. Algorithm: Label the two endpoints of the edge s and t. Delete the edge e from the graph. Perform a BFS on s and determine if it reaches t, keeping a counter of the distance, then add the deleted edge back in the graph. If it reaches t again, the graph contains a cycle containing e, otherwise it does not. Return counter + 1 if it reaches t again, otherwise return 0, representing no cycle.

Page 5...