COM 1201 Algorithms and Data Structures 2 - Spring 2000 - Homepage

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

Version of 4/2/2000

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 http://www.ccs.neu.edu/home/futrelle 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're not reading these pages, it's your problem I'm afraid. I won't make hard copies of every one of the course web pages to hand out in class, so always check on line. These web pages for the Spring course will be added to steadily as the Quarter proceeds, it will have some empty links for a while. If you want to see a complete web site for the previous version of the course, check the web pages for COM1201 Winter 2000.

The three threads of this course

This course has three threads, three different aspects of algorithms that are interleaved as the course proceeds. For the first two, we'll rely on our Sedgewick Algorithms textbook and for the latter we'll also use Lippman and Lajoie's C++ text:

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 will be expected to thoroughly understand certain programs in Sedgewick; I will tell you which ones you need to know. I generally do not ask you to write code on exams, but I will often give you code and ask you to discuss it in detail. There are various methods for analyzing and understanding code, which I'll discuss, but any approach should involve carefully studying the various statements and blocks in the code by using your Lippman and Lajoie book as a reference for the details. The book has good table of contents and an excellent index, so use it!

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 "industrial strength" software development system, Microsoft's Visual C++ IDE (Integrated Development Environment). It is a "visual" development environment with windows, mouse, cut and paste, drag and drop, etc. VC++ is used by many individuals and firms to develop commercial applications for Windows systems. 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 development system such as VC++ 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. We will not pay a lot of attention to abstract data types, templates and will not even use the Microsoft Foundation Classes (MFC), because all that machinery can get in the way of our understanding the "heart" of an algorithm, the simple and elegant ideas that makes it work. This is very much in the spirit of Sedgewick's text that focuses on the ideas behind algorithms and their implementation, rather than details of C++.

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 you won't have lectures and you'll need to do lots of 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. The only way to prepare yourself to write is to write -- simple enough! There's a lot of reading to do, so do not put off your reading -- you cannot successfully 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 assignments. Though I will sometimes assign entire chapters, I will always try to be specific about exactly what material from the chapters I expect you to learn and know well and just what pages you need to study. Details can be found in the COM1201 Course Syllabus and Calendar as well as on the Exam Information Page. There will also be individual pages posted describing upcoming exams, including some material from past exams. 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:
3/26/2000 -- first posting.
Institution:
Northeastern University, College of Computer Science, Boston, MA.
Instructor:
Professor Robert P. Futrelle   Email me at: futrelle@ccs.neu.edu.
Office:
115 Cullinane
Hardcopy mailbox:
161 Cullinane
Telephone:
Office 373-4239, Home 244-8261 -- both have voicemail
Teaching Assistant:
Jiang Zheng
Office : 23CN
Phone : 617-373-3822
Email : jiangzh@ccs.neu.edu
Office hours: Thur. 1-2pm, Fri. 1-2pm
Course Syllabus and Calendars:
See the separate page for the detailed Course Syllabus and Calendar for COM1201 Spring 2000. You can also access the official University_Calendar or a briefer version of it that I've prepared and there is a very brief "pocket calendar" for your reference.
Platform and development system:
This course will use Microsoft Windows on PCs and develop C++ programs using the Microsoft Visual C++ IDE (Integrated Development Environment) which I'll abbreviate VC++.
Textbooks:
Robert Sedgewick. Algorithms in C++, Third Edition   Addison-Wesley, 1998.
Stanley B. Lippman and Josee Lajoie C++ Primer, Third Edition Addison-Wesley, 1998.
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.
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 Tuesdays, 11:30-1:30.
College of Computer Science Tutoring:
There is help available both from ACM student volunteer tutors as well as scheduled help from graduate student tutors (sga's). See the schedules posted around the College. For ACM help see http://www.ccs.neu.edu/groups/acm/acmtutors/ For College help write or call the individuals on the posted list or to tutoring@ccs.neu.edu
On-line help:
For more info on most anything, search the web using google.com. Google uses a new and different algorithm from the other search services -- we'll discuss it. You should note that google does no "stemming". That is, if you search on "sorting" it will only look for that term, and will not include related forms such as, "sort", "sorts", "sorted", etc. Online sources of algorithm science and examples and systems include the SUNY Stony Brook collection developed by Skiena. There are also algorithm animation systems such as XTango, Samba and JAWAA (check them out using google.com). I will have my computer and a high-res projector at some of our class meetings, primarily to demonstrate how we can work with algorithms using VC++.
Project/Code Resources:
Here's an on-line copy of Sedgewick's C++ source code. You can cut and paste code from your browser into your source code buffers in VC++.
Classes:
Mondays, Tuesdays and Thursdays, 2:50 - 3:55. in room 312 Ell.
Recitations:
Fridays. Sec. A, 9:15-10:20 (Seq 8) or Sec. B, 10:30-11:35 (Seq. 9).
Labs:
Wednesdays. Sec. A: 2:50-3:55 (Seq. 8) or Sec. B: 4:05-5:10 (Seq. 9), but only when scheduled and announced in advance, in room 229 Cullinane. You will be assigned to one or the other of these two. Please attend only the one you've been assigned to, to prevent overcrowding. You may finish up the lab assignments anywhere else, but try to attend the first meeting to help you get started, ask questions, etc.
Exams:
There will be two quizzes, a midterm, and a final. All are closed-book, no calculators.
Grading:
Initially the distribution of credit will be: Quizzes: 20% (total), Midterm: 20%. Final: 35%, Labs: 25% (total). The distribution may be altered as machine problems and other assignments are added as the course proceeds.
Assignments
There will be a variety of written assignments and some machine problems; details will be provided later.
Attendance:
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