Instructor: Dean Allemang

Prerequisites:

Time and Place:

Textbook:

This is a marvelous book, that you will want to keep after you leave this class. Buy a copy of it, don't just borrow one.

Description.

A thorough knowledge of algorithms allows a computer scientist to determine what problems can be solved using a given amount of resources. The tools and techniques used for the basic algorithms covered in this course can be adapted to provide efficient solutions to novel problems.

The study of algorithms is mainly a mathematical study, in that it involves calculating the amount of time used for compound solutions given costs of basic operations, and theoretical limits on computations of certain problems. Therefore, homeworks will not involve a lot of programming, rather algorithm design and analysis. In the cases where programming is required, students may program in any language they please. The stress is on algorithmic design and clarity.

Course format:

Each class (except the first) will begin with a review of the homework from the week before (with presentations, when applicable), followed by presentation of new material.

Exams and Grading

Your final grade will be determined as follows: 35% homeworks, 30% midterm, 35% final.

Homeworks

The homepage for the course on courseinfo can be found here. If you have a BU Kerberos account, you use that name and password to access the site. If you do not, then write to me immediately, and I will provide you with guest access to the site. Because we only meet once per week, much of the course management will take place between classes, and will be managed from this web site. All homework assignments, course announcements, last minute changes, etc. will be managed in this way, so it is important that you have access to the site.

Policies

• You are responsible for all the material covered in lectures, readings and homeworks .  I will clarify what material is most  important before tests, however it is important that you do all the readings and review your class notes periodically.
• Class attendence is very important.  since there are so few class sessions, I will take attendance at all of them. Those who miss 2 classes may be dropped a full letter grade; those missing 4 or more receive a failing grade.
• Class participation is important.  Although the class is large, I encourage questions. Please don't be afraid to ask questions during a lecture, as this often means that many people may have a similar question, and it is worth stopping me.
• Homeworks are extremely important, since many of the topics require that your get your hands dirty and work through the problems.  I will do my best to choose homeworks that are fun to do, and that allow some latitude for creativity.
• There will be 12 regular assignments, roughly one per week (skipping weeks with major exams).
• Homeworks are due at 5pm on the day assigned, which will typically be the Monday after the homework was assigned. Since we will discuss homeworks at some length in calss, I will mark off 20% for each day late.  I will drop the lowest mark of the term. No exceptions will be made to this policy, so please don't ask.
• There will be no incompletes in this class except for reasons of dire illness near the end of a semester in which all previous work has been completed satisfactorily.
• You can not redo any assignment or do extra work after the semester is over to improve your grade - when the class is over, it is over.
• Students are encouraged to work together on homework assignments, though each homework submission should be a unique, creative solution, not just one solution turned in over and over again. Academic misconduct (plagiarism, cheating on exams) will not be tolerated, and will be reported immediately to the Academic Conduct Committee.

Course Outline

Week 1 - Sept 4, 2001. Administration.

Readings: Chapters 1-5

Homework 1 (due Sept 10): p. 11 1.2-5
p. 15 1.3-5 Write a program, 1.3-3
p. 31 2.1-4
p. 37 2.2-1, 2.2-7
p. 60 4.2-2
p. 64 4.3-1

Week 2 - Sept 11, 2001

Readings: Chapter 6, all sections except 6.4

Homework 2 (due Sept 17): p. 103 6.1-2, 6.1-7, 6.1-9
p. 114 6.3-1, 6.3-2

Week 3 - Sept 18, 2001

Readings: Chapters 7-8.

Homework 3 (due Sept 24):
p. 144 7.2-2, 7.2-3
p. 147 7.3-3
p. 149 7.4-2, 7.4-3
p. 156 8.1-3
p. 168 8-1

Week 4 - Sept 25, 2001

Readings: Chapters 9-10

Homework 4 (due Oct 1):
p. 175 9.1-3
p. 177 9.2-2, 9.2-3
p. 180 9.3-3
p. 191 10.3-1
p. 193 10-2 (a, b, and c only)

Week 5 - Oct 2, 2001

Readings: Chapters 11-12

Homework 5 (due Oct 8):
p. 203 11.1-6
p. 208 11.2-2, 11.2-5
p. 221 12.1-1, 12.1-2
p. 225-6 12.2-1, 12,2-3
p. 232 12.3-3, 12.3-5

Week 6 - Oct 9, 2001

Readings: Chapters 12-13

Homework 6 (due Oct 15):
p. 240 12.4-4, 12.4-5
p. 246 13,1-2,13,1-5
p. 250 13.2-2, 13,2-5
p. 253 13,3-2, 13.3-4, 13.3-5
p. 259 13-1

Week 7 - Oct 16, 2001

Readings: Chapters 14-15 Balanced trees, red-black trees, augmenting data structures

Homework 7 (due Oct 29):
p. 265 14.1-2, 14.1-3, 14.1-4, 14.1-5
p. 267 14.2-3, 14.2-4, 14.2-5
p. 272 14.3-1, 14.3-2, 14.3-4
p. 277 14.4-5
p. 286 15.1-4, 15.1-5
p. 289 15.2-2
p. 295 15.3-2, 15.3-3

Week 8 - Oct 23, 2001 ** Midterm Exam **

Week 9 - Oct 30, 2001

Readings: Chapter 16, sections 1-3

Homework 8 (due Nov 5):
p. 308-9 16.1-2, 16.1-4
p. 314 16.2-1, 16,2-3
P. 319 16.3-1, 16.3-2, 16.3-3
Due Nov 12: p. 324 16-2

Week 10 - Nov 6, 2001

Readings: Chapters 16, sections 1-3, 17, 1-3.

Homework 9 (due Nov 12): p. 333 17.1-2, 17.1-3
p. 324 16-2

Week 11 - Nov 13, 2001

Readings: Chapter 17, 1-3, chapter 18, 1-3.

Homework 10 (due Nov 19): p. 337 17.2-4
p. 344 17.3-1, 17.3-7, 17.3-8
p. 353 17-1
p. 360 18-1.1, 18-1.2
p. 363 18-2.1, 18-2.3

Week 12 - Nov 20, 2001

Readings: Chapters 22, sections 1-2, 24.

Homework 11 (due Nov 12):
p. 443 22-1.2, 22-1.3
p. 446 22-2.1, 22.2-3
p. 503 24-1.1, 24-1.2, 24-1.5
p. 510 24-2.4, 24-2.5

Week 13 - Nov 27, 2001

Readings: Chapters 34, 1-3

Homework 12 (due Dec 3):

Week 14 - Dec 4, 2001

Readings: Chapter 36