Course Information (links to past and current course materials)

Course FormatCourse Goals

Course Coordinator

Textbooks and References

Prerequisites by Topic

Major Topics Covered in Course

Laboratory Projects

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.

- Fall 2000 (one sections)
- Winter 2001 (one section)
- Spring 2001 (two or three sections)

BSCS03 required course

BSCS04 required course

BACS required core

BSIS required courseThis 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

rasala@ccs.neu.edu and york@ccs.neu.edu

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 Skills

Ý

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 evidenceComplexity, 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

7. types

8. signatures

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.

- Stacks, queues, linked lists, binary search trees, heaps, priority
queues, graphs

Searching, Sorting, Hashing, and Elementary Graph Algorithms

There are typically 3 or 4 projects - 2 weeks each.