HW 5Due: Wed Nov. 22CS105: Great Insights in Computer ScienceMichael L. Littman, Fall 2006Covering lectures 10 and 151. Flowchart GraphOn the next page is a graph I found on the web.a. Is it directed or undirected?b. Which nodes (A-G) are sources?c. Which nodes (A-G) are sinks?d. List a path that is a cycle.e. What’s the shortest path from D to E?exam styleFlowchart Graph (cont’d)ABCDE FG2. Find a Graph• Go online and find an example of a graph.• Choose four of the following to answer about the graph:- Is it directed/undirected?- What’s the longest cycle with no repeated nodes?- What’s the shortest cycle?- What’s the longest path with no repeated nodes?- Give a tour.- What are its connected components?- List its sinks.- List its sources.- Is it a tree? What’s the root?3. Random WaitsA.I flip a coin. How many times before heads comes up, on average?B. A roll a die. How many times, on average, before a composite number (4 or 6) comes up?C. I roll a die until I get a 1, then until I get a 2, then until I get a 3, then until I get a 4, then until I get a 5, then until I get a 6. How many times, on average, will I roll altogether?D.I start with the number 256. I flip a coin. If it comes up tails, I divide the number in half. How many flips, on average, before I reach “1”?exam style4. Something’s ROT13Decode this rot13 message.Ubj byq vf guvf wbxr nobhg ovanel? A
View Full Document
Unlocking...