Layer 2 Peter Ohring/Purchase College

Semester: Spring 2004

Instructor: Peter Ohring

Office: Natural Sciences Building 3002

Hours:

  • Tu,Th: 10:30-12:00

Phone: (914) 251-6678

email: peter@purchase.edu

Course Links:

Assignments

Assignments

Current Assignment

Homework 9 .. due Thursday April 29

  • Section 29: 1, 4, 5 , 6
  • Section 30: 2, 3, 4, 13, 16
  • Section 31: 1, 2, 6
  • Section 32: 1(a,c,e), 2(a,c,e), 3, 5, 8, 10, 13
  • Construct the Huffman coding trees and determine the average code-length for the following:
    Character Probability Code-string
    A 0.125
    B 0.25
    C 0.125
    D 0.5
  • Consider the Huffman coding for an arbitrary set of four characters (C1, C2, C3, C4) with corresponding probabilities:
    0 < p1 < p2 < p3 < p4 < 1.

    What conditions on p1, p2, etc. will ensure that the Huffman code will be the obvious one of length 2 (00, 01, 10, 11)?

Quote of the Week

Puzzle of the Week

General Remarks

Do not wait until the last moment to begin working on the assignment. Give yourself time to think about the problems, and ask the instructor and/or other students questions about the exercises. Mathematics is not a spectator sport. The only way to learn is to struggle with the material!

Your solutions should be complete and should include explanations in ..., yes, you guessed right, in English. The answers by themselves are unacceptable. I feel it is important that you learn how to write about mathematics.

Archived Assignments

Homework 1 .. due Thursday, January 29

  • Send me an email (peter@purchase.edu) in which you let me know something about yourself as it relates to this course: What is your computer background? What do you want to get out of this class? Your weaknesses? Strengths?

    In this email please provide an accurate email address at which you can be reached.

  • Section 1: 1(a,c,e), 4, 5, 8, 9
  • Section 2: 1, 2, 3, 4
  • Section 3: 1, 3, 6, 12

Homework 2 .. due Feb 5

  • Section 4: 1, 3, 5
  • Section 6: 1, 2, 4, 7, 8, 13, 14
  • Section 7: 1, 4, 5, 6, 9

Homework 3 .. due Thursday February 12

  • Section 8: 1(a,c,e), 2(a,c,e,g), 3(a,c,e), 5, 6(
  • Section 9:1(a,b,c,d), 2((a,b,c,d), 4(a,b,c,d)
  • Section 10: 1, 3, 5, 6, 12, 16(a,b,c)

Homework 4 .. due Thursday February 19

  • Section 11: 1(a,c,e), 2(a,c,e), 3(a,c,e), 5, 6
  • Section 12:1(a,c,e), 2, 3, 5(a,c,e), 7, 11(a,c)
  • The following questions relate to the circular diagram method (Hamming(7,4) code) of encoding messages.
    1. If you use the circular diagram method (Hamming(7,4) code) to encode the message 1011, what is the encoded message?
    2. Suppose the message 1010010 is received and decoded using the nearest-neighbor method. What message is recovered?
    3. What is the distance between received words 1011001 and 1000101?

Homework 5 .. due Thursday February 26

  • Section 13: 1, 2, 4, 7, 8
  • Section 14:1, 2, 3, 8, 9, 10, 12, 16, 17, 22, 27, 28

Homework 6 .. due Thursday March 4

  • Section 15: 1, 2, 3, 4, 5
  • Section 17:1, 2, 5, 7, 8
  • Suppose you have a Parliament with 3 parties and 101 seats (the U.S. congress has 2 parties and approximately 450 seats). How many ways are there to divide the seats among the parties? How many ways are there to divide the seats if each party gets at least one seat?
  • The following questions relate to (10, 2) error-correcting codes, that is, codes with 10 bits that correct 2 errors.
    1. What is the minimal distance between code words?
    2. Suppose 1101010001 is a code word. List 3 binary strings of length 10 that are corrected to to this code word. How many binary strings of length 10 are corrected to 1101010001?
    3. Give an upper bound on the number of possible code words.
    4. Combining two copies the repetition code of length 5 (a (5, 2) where the code words are 00000 and 11111) gives us a (10, 2) code with 4 code words (0000000000, 0000011111, 1111100000, 1111111111). The upper bound found in the previous question suggests that we can do much better than a code with 4 code words. Describe a (10,2) code that improves on this modified repetition code.

Homework 7 .. due Thursday April 1

  • Section 19: 3(a, c), 4(a, c), 8(a, b, e)
  • Section 20:1 (a, c, e, h), 2, 3, 4, 5, 6, 8, 9(a, c), 11, 12
  • Section 21:2, 3, 9
  • Additional Problems Using the Pigeonhole Principle:
    1. Prove that in a group of 13 people, at least two must have birthdays in the same month.
    2. Prove that in any group of six people there are at least three people who mutually know each other, or at least three people who mutually do not know each other.

Homework 8 .. due Thursday April 15

  • Section 26: 1, 3, 5 , 6, 7
  • Section 27: 2, 3, 4, 6, 7, 8, 9, 14, 17, 18
  • Section 28: 1, 2, 3, 4, 6, 13, 23, 24

New Media

Math/CS