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.
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.
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!
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++.
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 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.
Go to Syllabus and Calendar page for COM1201
Return to Prof. Futrelle's home page