Computer Science 275: Discrete Mathematics
Professor Craig C. Douglas
Teaching Assistant Ramakanth Kavuluru
 
001+002: Tuesday/Thursday 9:30-10:45 in CB 246
001: Wednesday 1:00-1:50 in RGAN 203
002: Wednesday 2:00-2:50 in RGAN 207
 
http://www.mgnet.org/~douglas/Classes/discrete-math
Notes: 1:1 2:1    Homework    Syllabus
Final Exam: May 3, 8-10 AM
 

Homework

Assignments

All homework will be from the textbook except for the programming assignments. You will see dates listed for when posted and when due. In general homework will be due on Wednesdays in the week after the posting date. Homework will never be due the next day. Watch this page since I will post new assignments on Tuesdays and Thursdays. You are responsible for watching this page and doing the assignments by yourself.

Name Posted Due Textbook Problems Programming
hw1 1/11/2007 1/17/2007 6th ed.: p. 19 (28, 38), p. 28 (4, 10)
Retyped (PDF)
 
hw2a 1/17/2007 1/24/2007 5th ed: p. 54 (20), p. 73 (2, 4)  
P1 1/17/2007 1/24/2007 None See P1.
hw2b 1/18/2007 1/24/2007 5th ed.: pp. 85-86 (22, 26)  
hw3 1/23/2007 1/31/2007 5th ed.: p. 95 (6), pp. 109-110 (8, 16, 34)  
P2 1/30/2007 2/7/2007 None See P2.
hw4 2/6/2007 2/14/2007 5th ed: pp. 205-206 (12, 20, 28)
p. 253 (6, 46), pp. 270-272 (6, 8, 26)
 
P3 2/14/2007 2/21/2007 None See P3.
hw5 2/15/2007 2/21/2007 5th ed.: pp. 310-311 (2, 8, 24), p. 319 (16), p. 342 (10), p. 348 (6)  
hw6 2/20/2007 2/28/2007 5th ed: p. 361 (16, 26), pp. 376-378 (4, 16, 18)  
hw7 2/26/2007 3/7/2007 5th ed.: pp. 392-394 (8, 16, 24)  
P4 3/1/2007 3/9/2007, 5pm   See P4.
hw8 3/21/2007 3/28/2007 5th ed.: pp. 409 (8a-c), pp. 423 (2, 4a-b), pp. 447 (2, 4a, 6b), pp. 464 (2, 4, 6)  
P5 3/21/2007 3/28/2007 None See P5.
hw9 4/3/2007 4/11/2007 5th ed.: pp. 480-482 (32, 48), pp. 494-495 (2, 18), pp. 513-514 (2, 18)  
hw10 4/5/2007 4/18/2007 5th ed.: p. 544 (2, 4, 6, 8), p. 554 (2, 6), pp. 563-564 (4, 8, 24), p. 575 (2, 4), p. 601 (2, 4)  
hw11 4/12/2007 4/25/2007 5th ed.: p.642-643 (4, 28), p. 658 (26), p. 673 (8, 12, 14), p. 686 (14, 16 applied to 14 only)  

Turn homework in at the start of your Wednesday section on the due date. Programs and their output should be turned in before the start of your Wednesday section using the online submission system. How many points you can accumulate in an assignment will be posted in the Grading section of this page.

Online Submission System

Programming assignments will be turned in using the computer science department's online submission system. To use it, follow these instructions:

  1. Open the website https://www.cs.uky.edu/CSAPP/main.php. You will see a login prompt.
  2. Your user name is your U-Connect user name (e.g., foobar2). Use your default U-Connect password.
  3. After you login there will be a set of links. One of the links will be Students. If you click on the link it will show all the courses you registered with the CS department. If it does not show the CS courses you registered for (possible in Internet Explorer) click the refresh link once and it will show them.
  4. Click on the CS27500x course link. Then you will see a new page with course details including Dr. Douglas' name, Rama's name, and Assignments: Here. Refresh the web page if you see a page with other material on it. Click the Here link to get to the assignment submission page. Click the submit link and upload your file (It must be a C++ file) for the corresponding assignment.
  5. The system will produces a message indicating that your file was successfully uploaded with a confirmation number which you should save until you get credit for the assignment. If you do not see this message, upload your file again (better safe than sorry).
The online program accepts multiple submissions. In case you submit more than one, only the latest one will be graded.

If you have trouble using the online system, contact Rama immediately.

Programming

All programming should be done in C++. Turn in a copy of your program, the input (if any), and the output. Include your name in the program and as the first line of your output. All programming should be done by yourself.

P1

Construct a complete truth table for a logic proposition. Given four variables (A, B, C, and D) and three operators (negation, conjunction, and disjunction), make up a proposition using all four variables and all three operators. Include in your program the proposition as a comment. Using nested loops, print out all values of the variables and the corresponding value of your proposition. Suggestion: Use 0 for F and 1 for T to simplify coding (i.e., simulate bit strings of length one for your variables).

P2

An important class of real-valued matrices are tridiagonal, denoted A = [ai,i-1,aii,ai,i+1]. Only the main diagonal and the ones directly above and below it are nonzero. Another important class of matrices are Toeplitz in which the diagonals of A are constants. A tridiagonal, Toeplitz matrix is one in which ai,i-1 = CL, aii = CD, and ai,i+1 = CU, i.e.,

[CD CU0 0 ... 0 ]
|CL CDCU 0 ... 0 |
A=|0 CLCD CU... 0 |
|... |
[0 0 CL CD]
Solving Ax=b is common in linear algebra. An efficient algorithm is to factor A=LU, where L and U have the form
[L1 0 0 ... 0 ]
|CL L20 ... 0 |
L=|0 CLL3 ... 0 |
|... |
[0 0 CLLn]
and
[1 U10 ... 0 ]
|0 1 U2 ... 0 |
U=|... ... |
|0 ... 0 1 Un-1|
[0 0 ... 0 1 ]
We can explicitly determine the elements of L and U using the following formulae:
CD =L1
CD =Li+CLUi-1,i=2,3,...,n
LiUi=CU, i=1,2,...n-1
Hence, you can determine

An interesting case is when CL = CU = 1 and CD = –2. Due to the pecularities of floating point arithmetic on computers, Li→Loo and Ui→Uoo, where both Loo and Uoo are constants depending on the number of digits stored in the floating point number.

Write a computer program that calculates Li and Ui for very large n's. What do you think the values of Loo and Uoo are? Turn in your C++ program, and a table with i, Li, and Ui for i = 1, 10, 100, 500, and 1000.

Turn in your C++ programs and output using the class online submission system. Rama will test your programs using g++.

P3

You are going to explore the efficiency of programs versus elegance of programming. Consider computing the Fibonacci sequence, which is defined both recursively and iteratively in the textbook and the class notes. You are to write in C++ two procedures to calculate the Fibonacci numbers fn: one recursive and the other iterative. For each procedure, you should report the value of fn and how many adds it took to calculate. Please review the static option when declaring a variable in C++ since it might make you program easier to write. Check your two procedures using the following n's: 0, 1, 2, 10, 20, 30, and 40. What happens when you try n = 50?

Turn in your C++ programs and output using the class online submission system. Rama will test your programs using g++.

P4

You are going to see how well Bayes Theorem holds up using an example from the class notes on page 117 (this example is not in the 5th edition of Rosen, but is in the 6th edition). You have two boxes. There are 2 green and 7 red balls in box 1 and 4 green and 3 red balls in box 2, respectively. We select a box at random, then a ball at random. If we picked a red ball, what is the probability that it came from the first box? On page 117, we showed that instead of the probability being 0.5 it is actually 0.645.

Write a C++ program to see if this is accurate. Write a procedure that selects a box and a ball. Call this procedure 10,000 times from your main program. There is a very nice tutorial on random numbers in C++ at http://www.daniweb.com/techtalkforums/thread1769.html that is worthwhile reading and even has useful code you may cut and paste into your own code.

There are several steps you need to do:

You are to print out at iterations 1, 2, 100, 500, 1000, 2000, 5000, and 10000 the iteration number and how many of your selections that were red balls came from box 1. At the end of iteration 10,000, print out the totals for how many green and red balls came from each of boxes 1 and 2.

Turn in your C++ programs and output using the class online submission system. Rama will test your programs using g++.

P5

You are going to implement integer multiplication using the recursive form defined on page 141 of the class notes as well as in an example in the textbook. You are to write a recursive function in C++ that takes two integers A and B and a bit length 2n, where both A and B are representable in 2n bits and are positive.

Your main program should read two positive integers A and B and 2n. Print these values. Then call your recursive function. Your recursive function should call itself three times with the products needed to calculate the product. Print the inputs A, B, and 2n and also the product computed. When your recursive function returns to the main program, print the final product.

You will get lots of output. Please devise a neat output scheme.

You should not try to debug your recursive function with a full 32 bit set of numbers. You should start with 2n=2, then 2n=4, 2n=8, ... If your code works with 2n=8, it probably will work with any 2n. The 2n=2 case is important since it represents the case when your recursive function cannot call itself again.

Turn in your C++ programs and output using the class online submission system. Rama will test your programs using g++.

Grading

HW1, due 1/17/2007, can garner a total of 80 points. Each part was worth at most 5 points. In truth tables, each wrong line adds 1 point to a maximum of 5 points. There were 16 parts, so the maximum number of points was 80.

HW2, due 1/24/2007, can garner a total of 55 points. Q1: 20 points at 5 per each of the 4 subproblems. For each subproblem: 3 points for each if the main statement is incorrect. Q2: 10 points at 2 per each of the 5 subproblems. Q3: 10 points, rain-fog question. 5 points for writing up using hypotheses using logic operators, 5 points for the steps to prove the result, and 1 point for every wrong step in the proof. Q4: 5 points, AB = \phi. What do you conclude 4 points if answer is both A and B are \phi. Q5: 10 points, show AB != BA iff A != B. 5 points for each direction in the above double implication with 9 points if only an example was provided.

P1, due 1/24/2007, can garner a total of 50 points. Each incorrect row was worth 2 points (up to 20 points), not using nested loops was worth 10 points, picking an invalid Boolean expression was worth 10 points, and a nonfunction program was worth 10 points.

HW3, due 1/24/2007, can garner a total of 58 points. Q1: 16 points at 2 per each of the 8 subproblems. Q2: 16 points at 2 per each of the 8 subproblems. Q3: 20 points at 5 per each of the 4 subproblems. For each subproblem: 1 point (if function is from N to N), 2 points for each condition on the function (1-1/onto/not 1-1/not onto), and 4 points if the function is not from N to N in the first place. Q4: 6 points at 2 per each of the 3 subproblems. For each subproblem: 1 point (the positive part of the solution) and 1 point (the negative part of the solution).

P2, due 2/7/2007, can garner a total of 25 points. Program did not run was worth 20 points. Incorrect output was worth 10 points. No limits or incorrect limits was worth 5 points. Only one limit missing was worth 2 points.

P3, due 2/24/2007, can garner a total of 40 points if program is not submitted: 10 points if the program does not compile or does not run, 10 points if iteration does not work, 10 points if recursion does not work, 10 points if output is missing, 3 points if addition counts are missing for iteration/recursion, and 2 points if addition counts are incorrect for iteration/recursion.

HW4, due 2/6/2007, can garner a total of 85 points. Q1: 10 points at 5 per each of the 2 subproblems (8 points if only examples are provided, 6 points if elements are not computed correctly, and 4 points if elements are computed using a summation, but the proof is ultimately incorrect). Q2: 8 points at 2 per each of the 4 subproblems (1 point off if an intermediate matrix is correct but the final answer is incorrect). Q3: 6 points@ 2 per each of the 3 subproblems. Q4: 10 points if not attempted. (9 points if the formula is incorrect and used induction on the wrong formula, 2 points if the base case is absent, and 6 points if the inductive part is absent). Q5: 20 points at 4 per each of the 5 subproblems (for each subproblem, 3 points if validity is correct and the function is incorrect or absent). Q6: 12 points at 3 per each of the 4 subproblems (for each subproblem, 2 points if the intial values are correct and the recursion is incorrect or absent). Q7: 10 points at 5 per each of the 2 subproblems (for each subproblem, 3 points if only basis is correct and the inductive part is incorrect/asbent, 3 points if induction is not used and the answer is incorrect). Q8: 9 points @ 3 per each of the 3 subproblems (2 points in only half of the 20 elements of S are provided for the first subproblem).

HW5, due 2/15/2007, can garner a total of 30 points. Q1: 4 points. Q2: 4 points (2 points if repetition is assumed). Q3: 4 points (1 point if ony one case was counted, 1 point if repetition is NOT assumed). Q3: 4 points (3 points for incorrect answers: 4 or 6). Q4: 10 points @ 1 for the first two subproblems, 2 for the next four subproblems (for each of the subproblems, 1 point if repetitions are NOT assumed 1 point if permutations are assumed 1 point if the roles of n and r are switched). Q5: 4 points (2 points if the algorithm was not followed, 1 point if all the subsets are not listed).

HW6, due 2/28/2007, can garner a total of 42 points. Q1: 10 points (5 points the wrong denominator, 2 points if the numerator does not consider 4 suits, and 3 points if the numerator does not compute a selection from the suit). Q2: 8 points (4 points if only atleast one integer was incorrect and 6 points for any other incorrect numerator). Q3: 8 points (4 each of the two subproblems and 2 points off if subsets are not considered as events). Q4: 8 points (4 points each for right hand side and left hand side). Q5: 8 points (2 points for a), 4 points for b), and 2 points for c)).

HW7, due 3/7/2007, can garner a total of 24 points. Q1: 8 points (1 point for every incorrect count for sum on the dice) Q2: 8 points (4 points each for right hand side and left hand side, 2 points if a formal approach viz. E(XY) = E(X)E(Y) is NOT used). Q3: 8 points (4 points each for incorrect computation of E(X) and E(X^2)).

P4, due 3/9/2007, can garner a total of 30 points if program is not submitted: 30 points if not submitted, 20 points if submission compiles but does not produce any meaningful output, 8 points for incorrect random number handling, 7 points for incorrect count maintenance, and 5 points for not displaying the output.

HW8, due 3/28/2007, can garner a total of 40 points. Q1: 6 points (2 points for each of the 3 subproblems and 1 point for each subproblem if a portion of the solution is missing or incorrect). Q2: 7 points (1 for each subproblem). Q3: 8 points (4 points for each of the 2 subproblems and for each subproblem, 3 points if only the characteristic equation is correct and 2 points if roots are correct but the solution is incorrect). Q4: 6 points (2 points for each of the problems and 1 point if the generating function has a missing term). Q5: 6 points (2 points for each of the problems and 1 point if the generating function has a missing term). Q6: 6 points (2 points for each of the problems and 1 point if the generating function has a missing term). Q7: 4 points (2 points if brute force is used and the incorrect solution and 2 points if inclusion-exclusion is used and incorrect solution is obtained). Q8: 4 points (2 points if brute force is used and the incorrect solution and 2 points if inclusion-exclusion is used and incorrect solution is obtained). Q9: 5 points (3 points off if brute force is used to get an incorrect solution and 2 points off if inclusion-exclusion is used to get an incorrect solution).

P5, due 3/28/2007, can garner a total of 30 points if program is not submitted: 10 points if code does not compile, 5 points if the base case for recursion is not handled correctly, 4 points if A0, A1, B0, B1 are not computed correctly, 6 points (2 for each of the three recursive calls and the addition of their results), and 5 points if no output is produced.

HW9, due 4/11/2007, can garner a total of 50 points. Q1: 8 points (1 for each of the 8 subproblems), Q2: 10 points (2 for each of the 8 subproblems, 2 points off if the answer is incorrect, and 1 point off if the answer is correct but the reasoning is incorrect), Q3: 8 points (2 for each of the 4 subproblems and 1 point off for each incorrect row of the matrices), Q4: 8 points (2 for each of the 4 subproblems), Q5: 10 points (2 for each of the 5 subproblems), and Q6: 6 points (2 for each of the 3 subproblems).

Cheers,
Craig C. Douglas

Last modified: