The CONTENT of this course is fairly well described by the ACM CS2 Suggested Curriculum, and by the requirements of 4-year schools to which our students want to transfer. The official description of the course is:
“Continues CS 210, with data structures and algorithm analysis. Students learn to create and use arrays, records, lists, stacks queues, binary trees, strings, and sets. Other topics may include searching and sorting, abstract data types, recursion, and hashing.”
What this means to me is that this is the course that gives the students their basic grounding in simple data structures, starting with lists, stacks and queues, and continuing through different types of trees, including heaps and B-trees.
In addition, we discuss Big-O analysis, and begin to look at algorithms themselves, to be able to make choices about “better” or “worse” solutions to problems. Object-oriented methodologies and theory are presented and practiced; and the students learn a second language, since we use C++ for our CS1 course, CS 210, and we use Java as the implementation language for CS 211.
As can be seen in the syllabus, we follow pretty much in order of our text, except that we hit extended classes sooner, so that the students can be working on their final project and so they understand the Java extended classes.
Our current text is Data Structures and Other Objects Using Java (Main & Savitch) . We use this text for several reasons:
• I personally like Michael Main’s style
• The logical progression of the concepts is well done, including using a “bag” class in various forms to give continuity
• The chapter exercises and reviews are very good
• and ... we have used his text through various languages, so it’s familiar!
The text is actually designed for a semester course, so we usually don’t get all the way through, although we do try... This quarter, for example, we will NOT be covering graphs because of time constraints.
Our schedule tends to be about 1 chapter per week - except that we take Stacks and Queues in one week, and the two Tree chapters in about a week and a half. This gives sufficient time to cover the material and practice it, and it also ensures that we do “get through” enough of the topics.
Several of the Why questions have been answered in previous documents... But, here goes:
1. Why THESE TOPICS?
a. The course “coverage” of topics is largely dictated by the ACM Suggested Curriculum for CS2; and by transfer issues to 4-year schools in this area. The topics are also partially determined by the textbook - which is based, again, on the CS2 Suggested Curriculum.
2. Why THIS ORDER?
a. I MOSTLY follow the book, since it conveniently follows a logical progression, supplying the students with needed information, especially where one concept builds on previous ones...
b. For example, we need to cover Linked Lists BEFORE we talk about implementing Stacks and Queues, which USE Linked Lists.... Recursion is needed before Trees, and so forth..
c. I cover EXTENDED CLASSES (Derived classes) EARLIER, than the book presents, because the students then can be thinking about their final project, and also understand the Java extended classes that they use.
d. I have tried various rearrangements, such as Searching and Sorting Earlier... but .. There is SO MUCH to discuss that it really needs to build in the way it is currently set up.
3. Why THIS LANGUAGE (Java)
a. Why Java? In a phrase - because UW-Seattle “requires” it. When we used Pascal, C, and C++, we talk almost the same concepts.... except the OOP had to wait for C++. But - the DATA STRUCTURES, the concepts of Abstract Data Types, Searching, Sorting, and so forth, have all remained the same, no matter the language. I would prefer C++, which I feel is easier and more powerful than Java; but - we make do with Java.
4. Other Comments
a. I include information about how the students will be evaluated, including my grading scale and late assignment policy, to help keep them informed.
b. The sections on Cheating and Special Needs are sort of “boilerplate” ones, strongly suggested by the school that we include.