MATH 131--Class Notes--Spring 08

PART III: Miscellaneous Topic

 

Monday, Wednesday, Friday, April 14, 16, 18, 2008: We discussed the Postnet code. It appears on almost every piece of mail and helps the post office sort large amounts of mail in an efficient manner. The Postnet code is encodes the zip+4 and sometimes the last two digits of the street address. In addition it contains a check digit. Every digit is encoded by a sequence of 5 lines, 2 of which are long and three of which are short. (The encoding can be found under the link above.)  The code has a guard bar, long line, at the beginning and another guard bar, long line, at the end. The check is the number that we need to add to the sum of the zip+4 (or zip+4+last two digits of street address) to get to the next multiple of 10. E.g., consider the address 18111 Nordhoff Street, Northridge, CA 91330-8313. If we use zip+4 then the sum of the digits is 9+1+3+3+0+8+3+1+3=31 and hence the check digit is 9. If we use the zip+4+last two digits of street address then the sum is 9+1+3+3+0+8+3+1+3+1+1=33 and hence the check digit is 7.

 

Monday April 21, 23: We worked on 

 

You are working for the campaign of a presidential candidate and your job is to monitor polling places. You must visit all 15 polling places, P1, P2, …, P15, in town spending as little time traveling as possible before returning to the campaign’s local headquarters which is also your starting point. You go to mapquest.com and find out the distances between the polling places plus the campaign headquarters. They are given in the table below. What should you do? Find a best (or maybe just a pretty good) route for you to take. How long is that route?

 

 

HQ

P1

P2

P3

P4

P5

P6

P7

P8

P9

P10

P11

P12

P13

P14

P15

HQ

*

10.4

8.6

6.7

5.3

8

14

7.9

8

3.8

3.7

10.7

11

2.4

8.4

9.9

P1

 

*

4.5

9.6

7.4

17.5

19.5

18

14

9.4

13

15

13.7

10.9

2.1

14.1

P2

 

 

*

5.2

3.3

13.5

15.1

14.6

9.7

5.3

9

14.1

9.3

7

3.7

9.7

P3

 

 

 

*

3.1

9.2

10

10.7

5

2.9

5.3

13.3

4.1

4.5

8

4.6

P4

 

 

 

 

*

10.3

12.3

11.4

6.6

2.1

5.8

11.6

7.1

3.8

5.4

7.5

P5

 

 

 

 

 

*

7.8

2.4

4.9

8.2

4.5

13

9.4

6.6

15.5

6.4

P6

 

 

 

 

 

 

*

10.2

6

11.2

10.4

20.4

8.4

11.6

17.7

5.4

P7

 

 

 

 

 

 

 

*

7.1

9.3

5.6

11.9

11.6

7.7

16.1

8.7

P8

 

 

 

 

 

 

 

 

*

5.2

4.5

14.5

4.5

5.6

12

2

P9

 

 

 

 

 

 

 

 

 

*

3.7

10.4

7

1.7

7.5

6.9

P10

 

 

 

 

 

 

 

 

 

 

*

10

8.3

2.1

11

6.5

P11

 

 

 

 

 

 

 

 

 

 

 

*

17.2

9

13.1

16.4

P12

 

 

 

 

 

 

 

 

 

 

 

 

*

8.3

12.1

3.6

P13

 

 

 

 

 

 

 

 

 

 

 

 

 

*

8.9

7.4

P14

 

 

 

 

 

 

 

 

 

 

 

 

 

 

*

12.5

P15

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

*

 
 
The class suggested the following solution: Start at HQ, go to the closest polling station 
which is P13 at distance 2.4 miles from HQ. Now go to the closest polling station to P13 
which is P9 at distance  1.7 miles form P13. Proceed in this manner. This is known as the 
nearest neighbor algorithm. It is an example of a “greedy” algorithm: at each step take the 
best you can get without looking ahead. 
 
This led some in the class to propose a modification of the algorithm. Abraham and Greg 
proposed to look ahead two steps. That is, calculate the length of all possible two step trips. 
So we need to find the lengths of HQ-P1-P2, HQ-P1-P3,…,HQ-P1-P15, HQ-P2-P3,…,
HQ-P14-P15. How many of them are there? Well, we can go to any of the 15 polling stations 
in the first step and from any of those 15 we can go to any of the 14 remaining polling 
stations. So there are 15 x 14 = 210 different 2-step paths and then pick a shortest one. 
While this would be annoying for us to do, a computer would have no problem with that.