Chapter Notes Algorithm Design

This page is a generated reference surface for selective reading. It exists to keep the learner apps guide-first while still preserving source access.

Learning objectives

• Explain the main ideas and vocabulary in Chapter Notes Algorithm Design.
• Work through the source examples for Chapter Notes Algorithm Design without depending on raw chunk order.
• Use Chapter Notes Algorithm Design as selective reference when learner modules point back to The Algorithm Design Manual.

Prerequisites

• None curated yet.

Module targets

• module-01-algorithm-analysis-design

AI companion modes

• Explain simply
• Socratic tutor
• Quiz me
• Challenge my understanding
• Diagnose my confusion
• Generate extra practice
• Revision mode
• Connect forward / backward

Source-of-truth note

This unit is anchored to The Algorithm Design Manual and the source chapter "Chapter Notes Algorithm Design". Use external resources only to clarify, extend, or modernize details without replacing the chapter's conceptual spine.

External enrichment

No chapter-specific enrichment resources are curated yet. Add them in the unit manifest when a source clearly improves learning.

Source provenance

• Primary source: The Algorithm Design Manual
• Source chapter: Chapter Notes Algorithm Design
• Raw source file: 074-chapter-notes-algorithm-design.md

Merged source

Chapter Notes Algorithm Design

Chapter Notes Algorithm Design

Chapter Notes Algorithm Design

5-12. [5] Thesquareof a directed graphG= (V, E) is the graphG2 = (V, E2) such that

(u, w)∈E2 iff there exists v∈V such that (u, v)∈Eand (v, w)∈E; i.e., there is

a path of exactly two edges fromutow.

Give efficient algorithms for both adjacency lists and matrices.

5-13. [5] Avertex coverof a graphG= (V, E) is a subset of vertices V′ such that each edge inEis incident on at least one vertex of V′.

(a) Give an efficient algorithm to find a minimum-size vertex cover ifGis a tree.

(b) LetG= (V, E) be a tree such that the weight of each vertex is equal to the

degree of that vertex. Give an efficient algorithm to find a minimum-weight vertex cover ofG.

(c) LetG= (V, E) be a tree with arbitrary weights associated with the vertices.

Give an efficient algorithm to find a minimum-weight vertex cover ofG.

5-14. [3] Avertex cover of a graphG= (V, E) is a subset of vertices V′ ∈V such that

every edge inEcontains at least one vertex fromV′. Delete all the leaves from any depth-first search tree ofG. Must the remaining vertices form a vertex cover ofG?

Give a proof or a counterexample.

5-15. [5] Avertex cover of a graphG= (V, E) is a subset of vertices V′ ∈V such that

every edge inEcontainsat least one vertex fromV′. Anindependent setof graph

G= (V, E) is a subset of vertices V′ ∈V such that no edge in Econtains both

vertices fromV′.

Anindependent vertex coveris a subset of vertices that is both an independent set and a vertex cover ofG. Give an efficient algorithm for testing whetherGcontains an independent vertex cover. What classical graph problem does this reduce to?

5-16. [5] Anindependent set of an undirected graph G= (V, E) is a set of vertices U

such that no edge inEis incident on two vertices of U.

(a) Give an efficient algorithm to find a maximum-size independent set ifGis a tree.

(b) LetG= (V, E) be a tree with weights associated with the vertices such that

the weight of each vertex is equal to the degree of that vertex. Give an efficient

algorithm to find a maximum independent set ofG.

(c) LetG= (V, E) be a tree with arbitrary weights associated with the vertices.

Give an efficient algorithm to find a maximum independent set ofG.

5-17. [5] Consider the problem of determining whether a given undirected graph G=

(V, E) contains atriangle or cycle of length 3.

(a) Give anO(|V|3) to find a triangle if one exists.

(b) Improve your algorithm to run in timeO(|V|·|E|). You may assume|V| ≤|E|.

Observe that these bounds gives you time to convert between the adjacency matrix and adjacency list representations ofG.

5-18. [5] Consider a set of moviesM1, M2, . . . , Mk. There is a set of customers, each one of which indicates the two movies they would like to see this weekend. Movies are shown on Saturday evening and Sunday evening. Multiple movies may be screened at the same time.

You must decide which movies should be televised on Saturday and which on Sunday, so that every customer gets to see the two movies they desire. Is there a schedule where each movie is shown at most once? Design an efficient algorithm to find such a schedule if one exists.

5-19. [5] Thediameterof a tree T= (V, E) is given by

maxδ(u, v)

u,v∈V

(whereδ(u, v) is the number of edges on the path fromutov). Describe an efficient

algorithm to compute the diameter of a tree, and show the correctness and analyze

the running time of your algorithm.

5-20. [5] Given an undirected graph Gwith nvertices and medges, and an integer k, give an O(m+n) algorithm that finds the maximum induced subgraph Hof G

such that each vertex inHhas degree≥k, or prove that no such graph exists. An

induced subgraphF= (U, R) of a graphG= (V, E) is a subset ofUof the vertices

V of G, and all edges Rof Gsuch that both vertices of each edge are inU.

5-21. [6] Letv andwbe two vertices in a directed graph G= (V, E). Design a linear-

time algorithm to find thenumberof different shortest paths (not necessarily vertex disjoint) betweenvandw. Note: the edges inGare unweighted.

5-22. [6] Design a linear-time algorithm to eliminate each vertex v of degree 2 from a graph by replacing edges (u, v) and (v, w) by an edge (u, w). We also seek to eliminate multiple copies of edges by replacing them with a single edge. Note that removing multiple copies of an edge may create a new vertex of degree 2, which has to be removed, and that removing a vertex of degree 2 may create multiple edges, which also must be removed.

Directed Graphs 5-23. [5] Your job is to arrangenill-behaved children in a straight line, facing front. You are given a list ofmstatements of the form "i hatesj". If i hatesj, then you do not want puti somewhere behindj, because then i is capable of throwing something atj.

(a) Give an algorithm that orders the line, (or says that it is not possible) in

O(m+n) time.

(b) Suppose instead you want to arrange the children in rows such that ifi hates j, theni must be in a lower numbered row thanj. Give an efficient algorithm to find the minimum number of rows needed, if it is possible.

5-24. [3] Adding a single directed edge to a directed graph can reduce the number of weakly connected components, but by at most how many components? What about the number of strongly connected components?

5-25. [5] Anarborescence of a directed graph Gis a rooted tree such that there is a directed path from the root to every other vertex in the graph. Give an efficient and correct algorithm to test whether Gcontains an arborescence, and its time complexity.

5-26. [5] Amothervertex in a directed graphG= (V, E) is a vertexvsuch that all other

vertices Gcan be reached by a directed path fromv.

(a) Give anO(n+m) algorithm to test whether a given vertex v is a mother of

G, wheren=|V| andm=|E|.

(b) Give anO(n+m) algorithm to test whether graphGcontains a mother vertex.

5-27. [9] Atournamentis a directed graph formed by taking the complete undirected

graph and assigning arbitrary directions on the edges--i.e., a graph G= (V, E)

such that for all u,v ∈V, exactly one of (u, v) or (v, u) is in E. Show that every

tournament has a Hamiltonian path--that is, a path that visits every vertex exactly once. Give an algorithm to find this path.

Articulation Vertices 5-28. [5] An articulation vertex of a graph Gis a vertex whose deletion disconnects G.

LetGbe a graph withnvertices andmedges. Give a simpleO(n+m) algorithm for finding a vertex of Gthat is not an articulation vertex--i.e. , whose deletion does not disconnectG.

5-29. [5] Following up on the previous problem, give anO(n+m) algorithm that finds a deletion order for thenvertices such that no deletion disconnects the graph. (Hint:

think DFS/BFS.) 5-30. [3]SupposeGis a connected undirected graph. An edgeewhose removal disconnects the graph is called abridge. Must every bridgeebe an edge in a depth-first search tree of G? Give a proof or a counterexample.

Interview Problems 5-31. [3] Which data structures are used in depth-first and breath-first search?

5-32. [4]Write a function to traverse binary search tree and return theith node in sorted order.

Programming Challenges

These programming challenge problems with robot judging are available at http://www.programming-challenges.comorhttp://online-judge.uva.es.

5-1. "Bicoloring" - Programming Challenges 110901, UVA Judge 10004.