COM 1201 Algorithms and Data Structures 2 - Introduction (1/6/99)

Winter 1999 -- Professor Futrelle
College of Computer Science, Northeastern U., Boston, MA

Course description, from the catalogue:

COM 1201 Algorithms and Data Structures 2 -- 4 QH

Continues the study of algorithms, data structures, abstraction, and encapsulation. Introduces structures that utilize arrays and/or links in more sophisticated ways. Studies linked lists, trees, heaps, priority queues, and hashing. Discusses efficient sorting (quicksort and heapsort) and introduces experimental analysis or algorithms. Examines several design issues, including selection of structures based on what operations need to be optimized (insertion, deletion, traversal, searching, sorting, evaluation), encapsulation of algorithms using class and template techniques, and how and when to use recursion (versus explicit stack-based techniques). Introduces graph algorithms and structures if time permits.

Prerequisite: COM 1101 or equivalent.

Description of this winter's course

The goals of this course are first, to introduce you to advanced data structures and algorithms described in the catalog description above. The second goal is to understand how these structures and algorithms are translated into a contemporary programming language. The take-home lesson is that the study of algorithms and data structures is fundamental and goes beyond their implementation in any particular language.

C++ is the language for the course. Despite its shortcomings, it has close relations to C and is widely used. (Many professionals feel that Lisp, Smalltalk, and Java deal with object-oriented programming in more sophisticated ways than C++.)

Check this website and your email frequently, to keep up with any additions and changes to the course -- go to my website at and then on to this page via the teaching link. Read all the COM1201 pages and reread any for which an update is indicated. If you do something wrong because you never read these pages, it's your problem, I'm afraid. I won't make hardcopies of every one of the course web pages to hand out in class, so always check on line.

The three threads of this course

This course has three threads, three different aspects of algorithms that are interleaved as the course proceeds:

In discussing the various algorithms in this course we will discuss some in detail, e.g., two lectures devoted to a single topic. Others will receive less attention, e.g., half a lecture. Some others will be mentioned quite briefly (no reading required) so that you'll at least be aware of them -- there are so many interesting algorithms in existence that I want you to at least be aware of them, even if you're not familiar with them in detail.

You'll become more self-reliant in this course

COM1100 and COM1101 are carefully designed to give you a lot of supporting software and help that warns you of errors and avoids crashes, etc. Of course in the "real world" you won't normally have such specially designed and supportive systems. COM1201 will accomplish some of the transition to the "real world". But you will have the support of an excellent "industrial strength" software development system, Code Warrior. It is a "visual" development environment with windows, mouse, cut and paste, drag and drop, etc. CW is used by many leading software companies to develop commercial applications for the Macintosh and PC. It has a debugger, and by always running in the debugger you can normally avoid crashes and you can examine the state of your system to see what went wrong. In addition, you can examine the contents of your data structures using the debugger without every having to write special print functions to see what the values are. Software should be designed correctly from the outset, but code invariably has problems, or is developed incrementally, so a good development system such as CW allows you to loop through the sequence edit, compile, run, debug, and edit again, quickly and efficiently.

You will learn to develop code from scratch by typing in code of your own or from the book or pasting in code from other sources or a combination of these. You'll learn to develop your own header and source files and get them compiled and linked and to use on-line documentation as you work. We will not pay a lot of attention to abstract data types, templates and the standard template library (STL), because all that elegant machinery can get in the way of our understanding the "heart" of an algorithm, the simple and elegant ideas that makes it work.

Reading assignments -- What you need to know

Another important aspect of self-reliance is learning from the textbook, rather than waiting to hear my lectures. You can get much, much more out of each lecture and out of the entire course, by reading the material before I cover it in class (and then reading it again, a few times). Again, in the "real world" (not MTV's version of it) you won't have lectures and you'll need to do more learning on your own, so start now! Also, if you do your reading before class, you may have specific questions about what you've read and if they don't get clarified in class, just ask some questions during class. Also, read actively, not passively -- have scratch paper and sketch pictures and write out bits of code as you read. What you have to do on tests is write, so write while you're learning. There's a lot of reading to do so do not put off your reading -- you cannot succesfully cram material of this complexity and detail -- if you try to cram, I'm sure you'll do poorly, so start right away and keep up.

You will be responsible on quizzes and exams for the material in your reading asignments. Though I will often assign entire chapters, I will always try to be specific about what specific material from the chapters I expect you to learn and know (details in the Course Syllabus and Calendar). Since talking's a lot slower than reading, there'll be material in your readings that you'll be responsible for that I can't go over in class or at least not in great detail. You are nevertheless responsible on quizzes and exams for what I have specified in your reading assignments, whether or not I cover it in class.

Asking questions:

Asking questions is smart. You might hesitate to ask questions, but you shouldn't. If you've read the assignments and listened to my explanations and feel confused, please ask questions. Asking questions just means that you're interested and you want to learn. No one should ever assume that because a person asks a question, they're dumb. It's quite the opposite. It's smart to ask questions -- and the answers make you smarter! Also, don't think that because other people don't ask questions, it's because they understand the material. That's often not true.

Major updates of these pages:
1/5/99 -- first posting.
Northeastern University, College of Computer Science, Boston, MA.
Professor Robert P. Futrelle   Email me at:
115 Cullinane
Hardcopy mailbox:
161 Cullinane
Office 373-4239, Home 244-8261 -- both have voicemail
Course Syllabus and Calendar:
See the separate page for the detailed Course Syllabus and Calendar. You can also access the official University_Calendar
Platform and development system:
This course will use Macintoshes, room 229CN and 201CN, and develop C++ programs using MetroWerks Code Warrior Pro, an excellent C/C++ development system. You can also look at these Macintosh Programming Pages.  If you do develop your code on any other system, you must compile and run it on the Macs and hand it in on a Mac disk. Because I use Lisp almost exclusively in all my work, I am willing to accept assignments done in Lisp, which we have on the Macs (Macintosh Common Lisp) and Unix (ACL). I will occasionally describe how the algorithms we study are implemented in Lisp to emphasize the fact that algorithms are ideas that go beyond any particular language.
Robert Sedgewick. Algorithms in C++  Addison-Wesley, 1992.
Books on algorithms in the library:
Algorithms is a big and important subject. Even the fastest computer in the world is useless without good algorithms. There are over one hundred books about algorithms in Snell library, at every level from beginner to research-level. Use NULIS at the Snell Library to check out what's there.

I have placed the following books on Reserve in Snell:
Personal Help:
If you need help at any time, find me in my office, call, or send email, or ask in class to set up an appointment. My office and advising hours are Wednesdays, 11:30-1:30.
On-line help:
On-line help is available from many sources. The basic Code Warrior manuals are on-line on the Mac server, Ambassador, accessible via the Documents folder. For more info on most anything, search the net at or using the new service Google uses a new and different algorithm than the other search services -- we'll discuss it. Online sources of algorithm science and examples and systems include the SUNY Stony Brook collection developed by Skiena, the XTango algorithm animation system, etc. I will have my computer and a high-res projector at most of our class meetings, both to demonstrate programming in CW and other environments and languages and to display web information.
Project/Code Resources:
All project files, source code, project documentation, etc. can be found in Ambassador:Course Directories:COM1201:Student. Here's an on-line copy of Sedgewick's C++ source code.
Tuesdays, 9:55-11:35, Wednesdays 3:30-5:10, Fridays, 9:55-11:35 in room 247CN.
There will be two quizzes, a midterm, and a final. All are closed-book. First quiz is January 27th.
Midterm: 20%. Final: 35%. Quizzes: 20%. Machine problems: 25%.
There will be a variety of written assignments and some machine problems; details will be developed as the course proceeds.
I will take attendance and it can affect your grade. When in doubt, come to class! We move through the material rather quickly, and without the explanations in class, and a chance to ask questions, you might become lost.

Go to Syllabus and Calendar page for COM1201

Return to Prof. Futrelle's home page