How Should Data Structures and Algorithms be
Taught
Danny KopecRichard CloseJim Aman
Senior Lecturer / Associate ProfessorProfessorAssociate Professor
Richmond,USCoastGuardAcademyWilmingtonCollege
The AmericanInternationalUniversityNew London, CTWilmington, OH
London,UK(860)444-8622(937)382-6661 X517
ABSTRACT
Data Structures and Algorithms is clearly a veryimportant topic and course in the Computer Sciencecurriculum. It has been taught at several levels by anumber of approaches. Should the approach bemathematical, theoretical and abstract or veryconcrete andhands on? Whichever method isused, the ultimate goal is the same: enhancingstudent comprehension. The panelists discuss threedistinct and well-defined approaches.
Keywords
Evaluating Teaching Methods, Computer ScienceEducation Research, Innovative InstructionalMethods, Impact of Technology on the Curriculum,Closed Laboratory Experience
1. Danny Kopec, Richmond, The
AmericanInternationalUniversity in
London
An undergraduate course in algorithms may betaught on a separate high pedestal, primarily tofourth year students. However, many chances ofrefinement have reinforced a combined approach thatemphasizes the teaching of data structures asimplemented by algorithms and some mathematicalmethods usingrecurrence relations and their proofs.This approach tackles traditional issues involvingchoice ofrepresentative data structures (arrays,linked lists, stacks, queues), but also considers theparticular problem at hand and its unique features.Two more extreme approaches might approach thesubject from different perspectives: 1) a problemsolving perspective which would look at typicalcomputer science problems, develop and analyzealternative solutions to them and then considerthem from the point of view of algorithmiccomplexity, practicality of implementation, andtransparency for the human programmer. 2) amathematical perspective which would teach anddevelop recurrence relationships for manyalgorithms. Years of experience with the coursehave led to an approach which combines the“discrete” almost cookbook approach of RobertSedgewick (Algorithms, 1988; Algorithms in C++.1992) with the continuous mathematical analysis,largely recurrence relation styled approach to thesubject by Gregory Rawlins (Compared to What,1991). Typical topics covered will include:elementary data structures, trees, recursion, analysisof algorithms, implementation of algorithms (that is,the first 8 Chapters of Sedgewick) followed by
Sorting Algorithms (Sedgewick, Chapters 8-13,possibly skipping Chapter 10 (Radix Sorting) andChapter 13 (External Sorting). Other TopicsSedgewick chapters covered will necessarilyinclude Elementary Searching Methods (Chapter14), Hashing (Chapter 16), and Graph Algorithms(Chapter 29, 3 I, and possibly 32). Optional topicsdepending on the rhythm of the course will includestring searching (Chapter 19) and cryptology(Chapter 23). Mathematical rigor and the curiosityof all involved is enhanced with Rawlins’s proofs ofthe complexity of diverse algorithms, including, forexample, esoteric methods like the Jump Search.This helps produce a course that is broad in itscoverage and sufficiently rigorous in its approach.
As a final course project students are asked todevelop programs investigating algorithms of theirchoice or to investigate course topics that couldnot be investigated in class, or to investigatecertain course topics, like cryptology, NP completealgorithms, Turing machines, etc. on their own andmake class presentations as well as produce shortpapers.
2. Richard Close, U. S. Coast Guard
Academy
Somewhere along the way in the undergraduatecomputer science curriculum, data structures andalgorithms have become algorithm analysis andcomputability. That is, the content of this coursehas tended to become more theoretical as thediscipline has matured and the latest curriculumrecommendations have appeared. Teaching a coursewith a large theory component is always achallenge but it seems that this one is especiallydaunting because it is likely to be the first time thatcomputer science majors come to grips with abstractmathematical concepts. This is somewhat surprisingbecause the assumption is that since CS majorsregularly deal with abstract concepts, they canreadily understand rigorous mathematical concepts.Some success has been achieved by including aclosed lab to provide an experimental component inthis course. The normal algorithms for selection,searching and sorting can be programmed andanalyzed experimentally. In addition, there are quitea few animations available for almost every well-known algorithm; now easily found on the Internet.Several industrious students have also found itfeasible to design and implement their ownanimations. It also is possible to include severalexercises on genetic algorithms, finite statemachines and computability. The operation of aclosed lab at this level is not trivial and may beunusual but the benefits seem to be worth the effort.Students appreciate the more concrete approach andtheir depth of understanding seems to be improved.
3. Jim Aman, WilmingtonCollege
One semester several years ago the Data Structuresclass produced an enrollment of only four students.
The instructor decided to conduct the course in aseminar format rather than the more traditionallecture/lab style. Since then the course has beenoffered three times in the seminar format, with amixture of results. The design of the course requiresextensive research, analysis, and testing of the datastructure or algorithm class assigned. Thedepartment has designated Data Structures a“writing-intensive” so the final report of the studentis also a major writing exercise. This report must bedistributed to the instructor and all class membersin “near-final” form at least one week prior to anassigned presentation date. The presentation is a 2+hour block in which the student presents the report,explains background, methodology, and otherrelevant information, and then submits to an openquestion-and-answer period. The audience isclassmates, other students (both lower- and upper-division), faculty from other departments, andalumni. All in all, it is an intense, high-energyperiod. There are several solid positives and glaringnegatives to this approach. First, the pressure of thepresentation is (by the students’ own evaluations) agrowth experience. They learn a great deal aboutliterature searches in a technical area. They alsolearn that one pass through the writing of ascholarly paper is not enough; the instructor’sediting is complete and demanding. From thepresentation itself and the Q&A period followingit, they learn a lot about themselves and about theimportance of maintaining emotional balance underpressure. There is, of course, a very significantdanger that a student might be pushed too far by theprocess. Fortunately, that has never happened. Butit is always a possibility. Second, mastery of abroad range of data structures and algorithms is notat all assured in the seminar format. If anythingtriggers a return to traditional format, it will be thisone factor. There is no question each studentbecomes master of the structure(s) and/or algorithmseach studies. No such mastery can be claimed forother structures or algorithms. Over the yearsstudents have always been asked to evaluate thecourse. Their responses have been quite uniform.The seminar/presentation format is difficult, but it isboth a welcome relief from lectures and definitely agrowth experience.