Advanced Discrete Structures, Winter 2013
Course Information and Syllabus

Assignments

Instructor:

About This Course

Advanced Discrete Mathematics presents the fundamentals of number theory for computer science; advanced counting techniques used in dynamic programming and analysis of divide-and-conquer algorithms; fundamentals of graph theory for network analysis, data mining, and software engineering; techniques for trees used for data transmission and storage and AI; and models of computation used in computer science theory.

The material depends on material from COMP 2300. Ingenuity is more essential than specific prerequisites beyond algebra.

Problem sets and exams will be primarily pencil-and-paper exercises, rather that programming assignments.

Course Meeting Times

The lecture is held 10:00-11:50am MW .

Text

Discrete Mathematics and Its Applications, ed. 7, Kenneth H. Rosen, ISBN 978-0-07-338309-5

Syllabus

Grading

Collaboration and Academic Honesty

When you turn in work in this course, you are implicitly agreeing that you have followed the rules for collaboration set forth for that assignment. In general,

• For problem sets, you may consult with the instructor, or fellow students. Do not do web searches for solutions.
• For the midterm exam, you must work individually.
• For the final exam, you must work individually.

Guidelines for Homework Assignments

You may certainly type your solutions, however, handwriting is acceptable as long as I find it to be readable, understandable and organized.

Please turn in paper copies in class on the due date. Problems turned in by "first call" will be graded and returned the following Monday. Students may turn in corrected solutions on the due date.

You may turn in one assignment for two-person groups. If you wish to work in a larger group, you may do so, but the writeups for the assignments should be independent.

Assignments will be posted here.

assigned: January 9, first call: January 16, due: January 23

section 4.1: 36, 40

section 4.2: 42, 44, 58

Problem set 2,

assigned: January 16, first call: January 23, due: January 30

section 4.3: 36, 42, 54

Problem set 3,

assigned: January 23, first call: January 30, due: February 6

section 4.4: 18, 20, 44

Midterm, takehome portion

assigned: January 30, first call: Febuary 6, due: February 13

section 4.6: 32

Chapter 4 Supplementary Exercises (pp. 308-309): 24, 38, 46

Hashing exercise: Consider the quadratic probe sequence h(k,i)=(k+i(i+1)/2)mod m where the table size m is a power of 2: m=2^n. Suppose the addresses are {0, 1, ... m-1}. Show that {h(k,0),h(k,1),...h(k,m-1)} = {0, 1, ... m-1}. That is, show that, for any key k, the probe sequence visits all addresses in the table.

Problem set 5,

assigned: February 6, first call: February 13, due: February 20

section 8.1: 16, 34, 36

section 8.2: 30, 40

Problem set 6,

assigned: February 20, first call: February 27, due: March 6

section 8.3: 18 (Recall that the recursive function may have to produce more than the required output.), 20

section 8.4: 24

section 8.6: 6, 18

Problem set 7,

assigned: February 27, first call: March 6, due: March 13

section 10.2: 32, 44

section10.3: 28, 44

section10.4: 16

Takehome Final

assigned: February 27, first call: March 13, due: March 15 (You may use the text and your notes to do this work. You may use a calculator for basic arithmetic. No other sources, interactive or otherwise, are permitted for this exam.)

section 11.2: Give the Huffman code for the symbol set with the following frequencies: a: 0.2, b: 0.1, c: 0.15, d: 0.22, e: 0.33. What is the average number of bits to encode a string of these symbols with these frequencies using the Huffmann code?

section11.4: 46

section11.5: 2 (Please show steps.), 6 (Please show steps.), 32