Course FormatCourse Goals
Textbooks and References
Prerequisites by Topic
Major Topics Covered in Course
Continues the study of algorithms, data structures, abstraction, and encapsulation. Introduces structures which 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 of 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; how and when to use recursion (versus explict stack-based techniques). Introduces graph algorithms and structures if time permit.
4 QH credit
Prerequisite: COM 1101 or equivalent.
BSCS03 required course
BSCS04 required course
BACS required core
BSIS required course
This is the third course for computer science and information science majors.
The course meets for three lectures per week in large sections (about 65 students).
There is one required one hour closed (supervised) lab per week.
The labs are typically taught by a graduate teaching assistant.
Main focus of homework is on programming assignments both large and small, some done in teams of two.
There is a written midterm and a final exam, and additional quizzes at the discretion of the instructor.
Starting in the Fall 2000 the course will use Java programming language.
Professor Richard Rasala and Bryant York
firstname.lastname@example.org and email@example.com
Goodrich and Tamasia, Data Structures in Java, 2nd Edition, John Wiley. Gnomon Copy Packets: to be announced Course web page: to be announced
Data Structures in C++ Using the Standard Template Library, Timothy Budd, Addison-Wesley, 1998. Stanley B. Lippman & Josée Lajoie, C++ Primer, Third Edition, Addison Wesley Longman, Reading, MA, 1998, ISBN: 0-201-82470-1.omputing Concets with C++ Essentials, John Wiley & Sons, Second Edition. http://www.cs.nwu.edu/academics/courses/c11/
Programming in the small1. program synthesisProgram design
2. write programs about 250 lines long
3. program analysis
4. use abstract data types
5. identify bugs in a small program and fix them
6. identify the base and recursive cases of a simple recursion
7. hand simulate a small piece of code1. select appropriate structure from alternativesProgram composition
2. use a standard structure and adapt it
3. evaluate the costs and benefits of using structures and algorithms1. knowledge of tools and environments
›Technical Judgement and Assessment
Quantitative reasoning1. scale and magnitudeQualitative reasoning and common sense
2. estimation and computation
3. ask whether an answer is reasonable.
4. simple 'back of the envelope' estimation and computation
5. exploration and experimentation techniques for collecting
6. quantitative data
7. experiments that test quantitative hypotheses.1. cost vs. benefitNature of evidence
2. engineering tradeoffs1. asking questionsSystem sense
2. controlling the variables
3. relevant situation
4. boundary case
5. global view1. perform diagnostic reasoning to isolate fault in a systemFactors in decision making1. role of theory in decision making
2. role of experiment in decision making
3. what kinds of evidence need to be considered
4. valid conclusions from given evidence
Complexity, Design, and Abstraction
Complexity1. system size and number of componentsMultiple views
2. interfaces between components
3. interfaces between a system and users
4. methods for managing complexity:
5. abstraction and encapsulation
6. standard components - STL1. selective suppression of detail
2. different views of the same thing
3. select appropriate view
4. information giving and hiding:
5. black box view
6. external interface as a contract
Students should be able to write small programs in C++, have been exposed to basic data types, the linked list data structure, the definition and use of classes in C++, and the basic control constructs of C++.› They also should have a basic understanding of how a computer works, what a vector and array are, and the notions of compilation, linking, loading and execution of a program.
There are typically 3 or 4 projects - 2 weeks each.