Homework 5

Due: See homework page
Directory name in your github repository for this homework (case sensitive): hw5

Skeleton Code

Some skeleton code has been provided for you in the hw5 folder and has been pushed to the Github repository resources. If you already have this repository locally cloned, just perform a git pull. Otherwise you’ll need to clone it.

If no Makefile is provided with the skeleton code, you will need to create one yourself. It should have a target for each of the executables in the programming portion.

Written Portion

Problem 1 - Counting (25%)

You must show work supporting your answer to receive credit.

Place your answers in a file counting.pdf.

Consider the word unusual
- How many unique subsets of 5 letters (of the 7) exist?
- How many different strings could be made from 5 of those 7 letters?
Using a standard deck of playing cards, how many ways are to form a 5-card hand with 2 pairs (i.e. pair of one value, a pair of a different value, and a fifth card of some other value)?
A violinist serenades couples at a romantic restaurant. She will play 16 songs in an hour and there are 7 couples. One couple is having a fight and will allow at most 1 song to be played to them before they ask the violist not to return to their table. If we care only about the number of songs each couple receives, how many ways can the songs be distributed amongst the couples.
There is a Binary Search Tree with 12 nodes. Each node has a distinct value between 1 and 12. The root has value 3, and its right child has value 9. How many possible Binary Search Trees could this be? Tip: Try to define how many ways there are to form a BST of 2 nodes. Then try to define how many ways there are to form a BST of 3 nodes (think about the possible insertion order based on rank: smallest, medium, largest) in terms of 2 node trees for certain cases. Continue to do this for 4 node trees (in terms of 3- and 2-node trees for various cases of insertion ordering based on rank) and 5 node trees.
10 friends arrive to get their COVID vaccine during a particular time slot. During that time slot there are 4 identical nurses administering shots, but 1 of the nurses may (or may not) be scheduled for a break during the time slot in which the friends arrive. Also, how long it takes the nurses to administer a shot varies wildly, so the nurses working during the time slot are guaranteed to serve at least 1 person, but how many additional people they are able to serve is arbitrary. How many different combinations (distributions) exist for how many of the friends each of the 4 nurses serve?

Problem 2 - Probability (25%)

You must show work supporting your answer to receive credit.

Place your answers in a file probability.pdf.

A professor has 15 students and during lecture will (uniformly) at random choose a student to answer a question. The professor asks 8 questions during the lecture. What is the probability no student will have to answer more than one question?
An integer from the range 00000 - 99999 is generated uniformly at random. We are interested only in even integers that start with 2 odd digits where all digits are unique. If we randomly generate 8 of these numbers in succession, what is the probability we get exactly 5 numbers that meet our criteria?
You roll 3 six-sided, fair dice. Let A be the event that at least 2 dice show 4 or above. Let B be the event that all 3 dice show the same value. Are A and B independent?
In poker, a flush is any 5-card hand where all the cards of the same suit. For this problem we will not distinguish between an ordinary flush and special flushes (like straight and royal flushes), meaning we will call any hand that has all 5 cards from the same suit a flush. Poker-player Paul loves a flush. What is the expected number of hands of poker he has to play to get a flush. (We assume each hand is dealt from a new deck containing of randomly ordered cards).
A basketball team has a superstar. When their superstar plays, they win 70% of the time. When their superstar does not play they win 50% of the time. Entering a 5 game stretch, the superstar had been recovering from an injury and said the chance they would play the next 5 games was 75%. You go on a trip to the jungle (no internet access). When you return you find out the team won 4 of the 5 games. What is the probability the superstar played those 5 games? You may assume the superstar doesn’t get injured during those games (either they play all or none of the 5).

Programming Portion

Problem 3 - Recursion, Counting, and Combinations (20%)

Consider an X by Y grid as shown below with the starting point of 0,0. Write a program to compute all possible pathways from point 0,0 (lower-left) to point X,Y (upper-right) that go through point x1,y1 (i.e. point 2,3 in the grid below), where 0 <= x1 <= X and 0 <= y1 <= Y. Furthermore, you may only go North (up) and East (right).

^                                           Finish
|   (0,5) - (1,5) - (2,5) - (3,5) - (4,5) - (5,5)
|     |       |       |       |       |       |
y   (0,4) - (1,4) - (2,4) - (3,4) - (4,4) - (5,4)
      |       |       |       |       |       |
    (0,3) - (1,3) -(x1,y1)- (3,3) - (4,3) - (5,3)
      |       |       |       |       |       |
    (0,2) - (1,2) - (2,2) - (3,2) - (4,2) - (5,2)
      |       |       |       |       |       |
    (0,1) - (1,1) - (2,1) - (3,1) - (4,1) - (5,1)
      |       |       |       |       |       |
    (0,0) - (1,0) - (2,0) - (3,0) - (4,0) - (5,0)
    Start                                     ---> x

Using your knowledge of counting you should be able to arrive at a formula for the number of possible paths. However, your program should print out all possible pathways where each path is a sequence of X,Y points.

For example, if the final location was 3,4 and you must go through 2,3, then the output of your program would be the following sequences (in any order you like).

0,0 -> 1,0 -> 2,0 -> 2,1 -> 2,2 -> 2,3 -> 3,3 -> 3,4
0,0 -> 1,0 -> 2,0 -> 2,1 -> 2,2 -> 2,3 -> 2,4 -> 3,4
0,0 -> 1,0 -> 1,1 -> 2,1 -> 2,2 -> 2,3 -> 3,3 -> 3,4
0,0 -> 1,0 -> 1,1 -> 2,1 -> 2,2 -> 2,3 -> 2,4 -> 3,4
0,0 -> 1,0 -> 1,1 -> 1,2 -> 2,2 -> 2,3 -> 3,3 -> 3,4
0,0 -> 1,0 -> 1,1 -> 1,2 -> 2,2 -> 2,3 -> 2,4 -> 3,4
0,0 -> 1,0 -> 1,1 -> 1,2 -> 1,3 -> 2,3 -> 3,3 -> 3,4
0,0 -> 1,0 -> 1,1 -> 1,2 -> 1,3 -> 2,3 -> 2,4 -> 3,4
0,0 -> 0,1 -> 1,1 -> 2,1 -> 2,2 -> 2,3 -> 3,3 -> 3,4
0,0 -> 0,1 -> 1,1 -> 2,1 -> 2,2 -> 2,3 -> 2,4 -> 3,4
0,0 -> 0,1 -> 1,1 -> 1,2 -> 2,2 -> 2,3 -> 3,3 -> 3,4
0,0 -> 0,1 -> 1,1 -> 1,2 -> 2,2 -> 2,3 -> 2,4 -> 3,4
0,0 -> 0,1 -> 1,1 -> 1,2 -> 1,3 -> 2,3 -> 3,3 -> 3,4
0,0 -> 0,1 -> 1,1 -> 1,2 -> 1,3 -> 2,3 -> 2,4 -> 3,4
0,0 -> 0,1 -> 0,2 -> 1,2 -> 2,2 -> 2,3 -> 3,3 -> 3,4
0,0 -> 0,1 -> 0,2 -> 1,2 -> 2,2 -> 2,3 -> 2,4 -> 3,4
0,0 -> 0,1 -> 0,2 -> 1,2 -> 1,3 -> 2,3 -> 3,3 -> 3,4
0,0 -> 0,1 -> 0,2 -> 1,2 -> 1,3 -> 2,3 -> 2,4 -> 3,4
0,0 -> 0,1 -> 0,2 -> 0,3 -> 1,3 -> 2,3 -> 3,3 -> 3,4
0,0 -> 0,1 -> 0,2 -> 0,3 -> 1,3 -> 2,3 -> 2,4 -> 3,4
20 solutions.

To compute these paths, we typedef a std::pair<size_t, size_t> struct as an XYPair where the first member of the pair is the x location and the second is the y location. You must implement the following function:

vector<vector<XYPair> > gridpaths(const XYPair& inter, const XYPair& final)

inter is the intermediate x1,y1 location all paths must go through and final is the final location of all paths. Remember, we assume we start from 0,0. The function should compute all paths and return them in a vector. Each path is itself a vector of XYPairs representing the sequence of locations travelled on that path. Thus, you will return a vector of vectors.

If final is 0,0 your should return an empty vector.

Requirements and Notes

Your solution must use recursion and no loops (but this will be the easiest approach anyhow).
You may define any helper functions you see fit (though they should not use loops either). Tip: having a helper function actually implement the recursive approach and always passing it a reference to a vector<vector<XYPair>> created by the outer function is likely the easiest approach to collecting all the paths. You’ll need more arguments than that for the helper, but this is how you can collect all the solution paths in a single vector.
We have provided a main() that you can use to test your program. It accepts 4 command line arguments being the intermediate x then y location followed by the final x then y location. gridpaths 2 3 3 4 would correspond to the example given above. If command line arguments are not provided it will default to 2,3 and 3,4 for the intermediate and final locations.
You should also have a Makefile target gridpaths that is run by the all target and produces your gridpaths executable.

Problem 4 - Recursion and Backtracking and Boolean Satisfiability (30%)

An important problem in several contexts (computer-aided design tools, theorem provers, etc.) is boolean satisfiability. It seeks to answer whether there exists an assignment of 0’s (false) and 1’s (true) to binary variables {x1, x2, …, xn} that will cause a Boolean expression (AND, OR, NOT) to evaluate to true. The Boolean expression format we will use is called conjunctive normal form (CNF) and an example is shown below:

(x1 || x2 || !x4) && (x3) && (!x1 || !x2)

We call each term in parentheses a clause. Notice all clauses are AND’ed together but within each clause is the OR’ing of variables or their negations. Thus, for the entire expression to be true, ALL clauses must evaluate to true.

In this example, the following assignment will cause the expression to evaluate to true:

x1 = 0
x2 = 0
x3 = 1
x4 = 0

This expression has no assignment that causes it to evaluate to true

(x1 || x2) && (!x2) && (!x1 || x2)

The expressions will be given as a text file in a format used by many researches to benchmark their algorithms known as the DIMACs format:

c comment here
p cnf num_vars num_clauses
clause 1
clause 2
...

The first example we showed above would be represented in the DIMACS format as:

c this file mimics the first example above
c assume this file's name is test.cnf
p cnf 4 3
1 2 -4 0
3 0
-1 -2 0

Here each variable is represented by it corresponding number (starting at 1) in the clause and negative numbers indicates the variable should be ‘NOTed’/inverted (i.e. must be False to make the clause True). Each clause ends with a 0 just to indicate the end of the line (this isn’t really necessary but is part of the DIMACS format) and you can just discard it. Just to reinforce this: 0 is not a variable but an end of clause delimiter.

Your task is to write a program (named sat_solver.cpp) that reads in one of these DIMACS CNF expressions from a file (provided as the 1st argument on the command line), use a recursive backtracking search to attempt to find a satisfying assignment of 0’s (False) and 1’s (True) such that the expression evaluates to true. Your program should output (as a file whose name is specified as the 2nd argument on the command line) an assignment of variable values if a solution is found (you need only find the first solution and not ALL solutions) or No solution if no solution exists.

So running the program (using the test.cnf file shown above)

$ ./sat_solver test.cnf test.out

should cause an output file, test.out, to be generated containing:

= 0
= 0
= 1
= 0

An expression w/o a solution should generate a file whose contents are simply:

No solution

Remember you must use a recursive backtracking search approach to get any credit for this problem. To that end, backtracking search in this context should simply try to start assigning one variable at a time and seeing if a solution is found, still possible, or not possible. To do this, each variable should likely have 3 states: {Undecided/unassigned, False, True}. As you make an assignment to a variable you’d want to check its effect on the formula. Recall, since all the clauses are AND’ed, EVERY clause must evaluate to true. When that happens you know you have a solution. If even one clause evaluates to false, your assignment is not valid and must backtrack. Some clauses may not have enough information yet to determine true or false (i.e. they are Undecided) and thus means the current assignment is okay thus far but requires us to assign additional variables.
So the easiest implementation approach is to recurse through the variables and try assigning each option (True, False) and if you have to return/backtrack, change the variable back to undecided. Note that both variables can be undecided (if they are not assigned yet), as can the value of an entire clause (if no term in the clause evaluates to true after negation, if needed). The formula is not satisfied until all clauses are TRUE. We have provided an enumeration type (enum TruthVal { UNDEC = -1, ZERO = 0, ONE = 1};) for undecided, zero, and one that can be used both for variable assignment and the status of clauses, if desired.

We may find a solution that satisfied all the clauses with some variables still being unassigned. This indicates their value does not matter. In that case, you must NOT output those undecided variables to the output file.

Finally, you MUST maintain a map (not an array or list) of each variable to its current value (0, 1, or Undecided). Start by using std::map but once your program works, we strongly encourage you to instead use your AVLTree<K,V>. We have provided a typedef: typedef std::map<int, TruthVal> VarValueMap; so that if you write your code using VarValueMap as the map type, then you should need only #include "avlbst.h" and change that typedef from std::map to AVLTree. Also, we ask you to return to this problem and use a HashMap implementation from a future homework. Note: you will need to copy over your avlbst.h, bst.h, and print_bst.h files to your hw5 folder.

Feel free to generate your own CNF files and post them on Piazza along with the solutions. We provide some larger test files in the uf20 subdirectory of the resources/hw5 repo/folder. These tests are ALL satisfiable. We cannot give a solution to each because so many may exist and we may all get different assignments. You should use these as test cases ONLY after working with smaller tests (maybe some additional hand-written cases that you create).

As always, no memory leaks should be present in your program and you MAY NOT use global variables.

You should also have a Makefile target sat_solver that is run by the all target and produces your sat_solver executable.

WAIT You aren’t done yet. Complete the last section below to ensure you’ve committed all your code.

Commit then Re-clone your Repository

Be sure to add, commit, and push your code in your hw5 directory to your hw-username repository. Now double-check what you’ve committed, by following the directions below (failure to do so may result in point deductions):

In your terminal, cd to the folder that has your resources and hw-username
Create a verify-hw5 directory: $ mkdir verify-hw5
Go into that directory: $ cd verify-hw5
Clone your hw_username repo: $ git clone git@github.com:usc-csci104-summer2022/hw-username.git
Go into your hw5 folder $ cd hw-username/hw5
Switch over to a docker shell, navigate to the same verify-hw5/hw-username/hw5 folder.
Recompile and rerun your programs and tests to ensure that what you submitted works. You may need to copy over a test-suite folder from the resources repo, if one was provided.