---

Course Information

Instructor	V. Paul Pauca (paucavp AT w f u DOT e d u)
Time:	T - Th, 9:30 - 10:45, Manchester 244
Office hours	Tuesdays: 10:45 - 11:30 am, Wednesday 2:00 - 3:00pm
Syllabus	PDF
Textbook	Algorithms - Dasgupta, Papadimitriou, and Vazirani

---

Homework Assignments

• HW-1: 0.1 (b,d,f,g,i,k,l,m) (8 pts); 0.2 (a-c) (9 pts); 0.3 (a-c) (6 pts). Due: 9/4
• HW 2: Exercises: 1.2, 1.10, 1.11, 1.12, and 1.18 (15 pts). Due: 9/18
• HW 3: Exercises: 1.20, 1.21, 1.25, and 1.28. Due: 9/30
• HW 4: Exercises: 2.3 (3 pts), 2.4 (3 pts), 2.5 (5 pts). Due: 10/30
• HW 5: Exercises: 2.15, 2.17, 2.28 (3 pts each). Due: 11/4
• HW 6: Exercises: 3.1 (1 pts), 3.2 (2 pts), 3.4 (4 pts), 3.8 (4 pts) Due: 11/18

---

Programming Assignments

• Modular arithmetic and RSA cryptosystems: Assignment description [pdf]
  Sample GMP code and Makefile.
• Shortest paths in undirected graphs: Assignment description [pdf]
  • DIMACS New York and Rome distance data.
  • Physical coordinates for the New York data can be found here.
  • Table of results
    Shortest Path Plot:
    

    Student	Minimum cost (feet)	Time (s)
    	74198	0.255
    	74198	1.953
    	74198	2.142
    	74658	4.91
    	79530	15
    	35743228	4.37

---

Resources

• The GNU MP bignum Library: GMPLib.org
• How to install GMP on Windows systems: NYU notes
• Matlab code for exploring the DFT and the FFT: [fftcode.tar.gz]

---