COM 1201 Algorithms and Data Structures 2

Course Description and Catalog Information
Course Information (links to past and current course materials)
Course Format
Course Coordinator
Textbooks and References
Course Goals
Prerequisites by Topic
Major Topics Covered in Course
Laboratory Projects

Course Description

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.

Course Information

Course is offered during the Fall, Winter and Spring quarters. CS majors are guaranteed a place in class.

Course Format

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.

Course Coordinators

Professor Richard Rasala and Bryant York
rasala@ccs.neu.edu and york@ccs.neu.edu

Textbooks and References

Fall 2000
  • Goodrich and Tamasia, Data Structures in Java, 2nd Edition, John Wiley.
  • Gnomon Copy Packets: to be announced
  • Course web page: to be announced
    • Spring 2000
  • 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/

    • Course Goals

  • Programming Skills

    • Ý
    Programming in the small
    1. program synthesis
    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 code
    Program design
    1. select appropriate structure from alternatives
    2. use a standard structure and adapt it
    3. evaluate the costs and benefits of using structures and algorithms
    Program composition
    1. knowledge of tools and environments
  • ÝTechnical Judgement and Assessment

    • Ý
    Quantitative reasoning
    1. scale and magnitude
    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.
    Qualitative reasoning and common sense
    1. cost vs. benefit
    2. engineering tradeoffs
    Nature of evidence
    1. asking questions
    2. controlling the variables
    3. relevant situation
    4. boundary case
    5. global view
    System sense
    1. perform diagnostic reasoning to isolate fault in a system
    Factors in decision making
    1. 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


    • Complexity

    1. system size and number of components
    2. interfaces between components
    3. interfaces between a system and users
    4. methods for managing complexity:
    5. abstraction and encapsulation
    6. standard components - STL
    Multiple views
    1. 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

    Prerequisites by Topic

    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.

    Major Topics Covered in the Course

    Laboratory projects

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