Exam 3

You may use 4 contiguous hours on this exam. You may use any resources on this exam, except for other people. See also the course policies.

Put all your answers in one CodeSkulptor file. Submit your CodeSkulptor URL on OWL-Space, under Exam 3.

---

To save you time, we have provided code in a template.

The following are expected in all code you write:

• Wherever appropriate, use functions/methods that have been defined previously.

• Wherever appropriate, separate repeated code into helper functions.

---

One common use of graphs these days is to model social relationships such as formed by Facebook friends. These graphs are undirected, because the fundamental relationship of friendship is undirected — if someone is your friend, then you are their friend. (Terminology: The relationship is symmetric.)

In the following two problems, you will explore two kinds of groupings of people based upon social relationships. In addition, both represent common graph concepts that are widely applicable beyond social graphs.

You are provided a Graph class for undirected graphs. You should use this class, and there is no need to edit that code.

1. (15 points)

   One type of social group is exemplified by the close and frequent interaction of the members. These groups are known both in the social sciences and in common parlence as cliques are most associated with high school kids (the “jocks”, the “geeks”, etc.)

   In graphs, a clique has a very similar definition. It is a subset of nodes that are fully connected. In our social graph example, this means that within a clique, every pair of people are friends. Nodes in a clique may have edges to nodes outside the clique, as well.

   It turns out that finding cliques is a classic hard (Terminology: NP-Complete) problem. You will solve the much simpler problem, determining whether or not a given set of nodes (i.e., people) form a clique. Repeating the definition, the set is a clique if every pair of nodes in the set have an edge between them.

   Define is_clique(node_set, graph). It returns whether or not the given set of nodes forms a clique in the given graph. Note that you should also verify that the given nodes are even in the graph.

   Several test examples are in the template.

2. (25 points total)

   On the other hand, we can think of very loosely associated social groups. One possible definition of a community is that for every pair of people in the community, there is some chain of friendships between them. Worded another way, your community is all of the people with whom you are connected by the friends relationship, even if the connection is distant, e.g., friends-of-friends-of-friends-of-friends.

   In graphs, this concept is called a connected component. A connected component is a subgraph in which any two nodes are connected, directly or indirectly, and which is not connected to any other node. (Follow the previous link for a pictorial example.)

   Referring back to one other concept that we saw previously, the connected components of a graph form a partition of the graph. For example, in the stereotypical high school where the social groups are clearly separated, the connected components might represent the “cool kids”, the “artsy kids”, and the “nerds”.

   The following is one algorithm for finding the connected components. Throughout, we will maintain a list of sets of nodes that partition the graph. We start with small, easily identified sets of connected nodes, and then combine these repeatedly as the algorithm discovers edges between them.

   1. Let components be a list of set of nodes such that each graph node is in a set by itself.
   2. For each edge in the graph,
      1. Let node1 and node2 be the end points of the edge.
      2. Let component1 and component2 be the sets in components that contain node1 and node2, respectively.
      3. If component1 and component2 are different sets, then remove both sets from components, and add their union to components.
   3. Return components.

   Define a function connected_components(undirected_graph) that returns the components computed by the above algorithm.

   A test example is in the template.

In the next problem you will complete the implementation of a simple Blackjack program. If you are not familiar with the game, use the previous link and read the first few paragraphs.

3. (60 points total)

   You are given incomplete versions of Player, Deck, and Card classes. A Card object represents one playing card. A Deck object represents a collection of those cards that have not been dealt to a player. A Player object represents a player, who has a collection of cards and a strategy of how to play.

   Since we have not created interactive programs in this course, you will write code for the players to play a game without any outside intervention. This means the players each need some strategy for deciding when to hit (get another card) or stand (don't get another card). For this program, the strategies will be extremely limited — stand if the hand's value is at or above a certain cutoff. Each player can have a different cutoff.

   1. (40 points total)

      Complete the provided classes. See the template's comments for additional details.

      • (5 points) Card class: __init__() method
      • (5 points) Deck class: __init__() method
      • (5 points) Deck class: deal() method
      • (5 points) Deck class: deal_card() method
      • (5 points) Player class: __init__() method
      • (5 points) Player class: hit() method
      • (5 points) Player class: add_card() method
      • (5 points) Player class: is_busted() method

   2. (20 points)

      Define play_game(player_names), which takes a list of the player's names. It creates the specified number of non-dealer players, plus one dealer. The non-dealer players each stand at or above a random value between 15 and 18. The dealer stands at or above 17. It creates, shuffles, and deals two cards to each player. Each player plays, with the dealer going last. Each non-dealer player checks if they won.

      If a player is busted, they lose — even if the dealer is also busted. If the dealer is busted, each non-busted player wins. Otherwise, a player wins, loses, or ties depending on whether his score is greater than, less than, or equal to the dealer's score.