COM 1201 Algorithms and Data Structures 2 - Homepage

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

Updated 2/3/2000 (includes latest TA contact information)

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 never read 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.

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 "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.

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 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. 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 often 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. Details can be found in the COM1201 Course Syllabus and Calendar as well as through 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:
1/2/2000 -- first posting. This is the version of 2/3/1000.
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 for Labs:
Arvind Meda
Office : 21 Cullinane Hall
Phone : 617 373 5204
Email : arvind@ccs.neu.edu
Teaching Assistant for Homework, general help:
Yuchun Guo
Office : 53 Cullinane Hall
Phone : 617 373 4607
Email : guo@ccs.neu.edu
Office hours: Tuesdays, 12-2; Thursdays, 11-2.
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 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.
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 than 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, 4:05 - 5:10. in room 312 Ell.
Labs:
On Thursdays, only when scheduled and announced in advance, in room 229 Cullinane. There will be two sessions. One starting at 2:50 and the other starting at 5:20. You have been assigned to one or the other of these two. Please attend only the one you've been assigned to, to prevent overcrowding. You may work on the lab assignments at home, but you must attend the lab first.
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 (each): 10%, Midterm: 30%. Final: 50%. The distribution will 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