|
|
|
|
| Instructor: Gábor Hetyei |
Last update: |
|
| Disclaimer: The information below comes with no warranty. If, due to typocraphical error, there is a discrepancy between the exercise numbers announced in class and the numbers below, or this page is not completely up to date, the required homework consists of those exercises which were announced in class. Check for the time of last update above. If, by my mistake, a wrong exercise number shows up below, I will allow you extra time to hand in the exercise whose number was announced in class. If, however, exercise numbers are missing because this page is not up to date, it is your responsability to contact me before the due date. (No extra time will be allowed in that case.) This page is up to date if the last update happened after the last class before the next due date. |
Notation: 1.2/5 means Exercise 5 in Chapter 1, Section 2.
| No. | Date due | Problems |
| 13 | Tuesday April 29, 2003 | 5.3/2,4,8 5.4/2. |
| 12 | Tuesday April 22, 2003 | 5.1/12 5.2/4,6,14 Write up the incidence matrix for Fig 7.1 on page 272 (represent a loop with a zero row). |
| 11 | Thursday April 17, 2003 (note extended deadline) |
4.7/4,6,8b (explain your answer) 5.1/2,4,5,6. Bonus: Describe those digraphs whose adjacency matrix is nilpotent (=some high enough power of the matrix is zero). |
| 10 | Tuesday April 8, 2003 | 4.5/2,6,14,16,18 Look at the solution of 4.5/17 in the back of the book and draw the depth-first-search tree which yielded the solution. (Number the vertices.) Assume that the root of the DFS tree is at f. 4.7/2. |
| 9 | Tuesday March 25, 2003 |
Breadth-first search for the Petersen graph (Fig 4.7 on page 250). 4.3/2,12 Demonstrate that the Petersen graph is isomorphic to the graph whose vertices are the 2-element subsets {i,j} of {1,2,3,4,5} and edges connect the pairs of disjoint subsets. (So {1,2} is connected to {3,5} but not to {2,4}.) 4.4/3,10,14,19. |
| B1 | Thursday March 27, 2003 | Bonus Quiz 1 |
| 8 | Tuesday March 18, 2003 | 4.1/2,6,14,16,18 4.2/2,6. |
| 7 | Tuesday March 4, 2003 | 3.2/14,22,23 3.4/1a,2,7,10. Give a closed formula for the sequence defined by a0=1, a1=1, and an+2=5an+1-6an. Note: to answer some of the questions you may want to use the handout on Fibonacci type sequences. |
| 6 | Tuesday February 25, 2003 | 3.1/2,8,9,12 3.2/4,5 |
| 5 | Tuesday February 18, 2003 | 2.3/1,2,4,6,13. |
| 4 | Tuesday February 11, 2003 | 2.1/2,12,22 2.2/2,7,8,14ab. |
| 3 | Tuesday February 4, 2003 | 1.4/2,7,14,15 1.5/3,8,28,31. (No new problem was assigned on Thursday.) |
| 2 | Tuesday January 29, 2003 | 1.3/6,9 (without the case when there is a chair on the social committe),17b,20b. Bonus: 1.3/32. |
| 1 | Tuesday January 22, 2003 | 1.1/1,5,7 1.2/2,5,10,26b (part "a" was done in class) 1.3/3 (just give the number of the subsets, do not list them!), 5. Bonus: 1.1/17 |