Lecture: 3 hours
Discussion: 1 hour
Prerequisites: Courses 20, 40 (C++ and UNIX); and a grade of C- or better in each course
Grading: Letter; based on the programs (5 @ 5% each), written homework (5%), two midterm (30%), final (40%)
Catalog Description:
Design and analysis of data structures for a variety of applications. Trees,
heaps, searching, sorting, hashing, graphs. Extensive programming.
Expanded Course Description:
A systematic study of data structures, including stacks, queues, lists, skip lists, trees, binary earch trees, AVL trees, splay trees, B-trees, priority queues, hash tables, and the union/find data structure. Analysis of algorithms, including sorting, graph algorithms, topological sort, depth-first search, shortest path, minimum spanning tree. Amortized analysis. If time permits, any of the following topics: tries, Huffman codes, branch-and bound, digital search trees, Fibonacci heaps, network flow, and critical path analysis.
Textbook:
M. Weiss, Data Structures and Algorithms in C++, Addison Wesley,
2006
Computer Usage:
Students will utilize the computer systems in the Computer Science Instructional
facility (or their home computers) to develop 4 large programs.
Engineering Design Statement:
Programming assignments involve design of the proper data-structure, design
of the associated program, coding, and testing of open-ended problems
requiring independent solution by the students. The function of the programs
are specified, but design details of possible solutions are not specified.
Engineering design skills are further developed by increasing the complexity
and open-ended nature of the assignments throughout the term.
ABET Category Content:
Engineering Science: 2 units
Engineering Design: 2 units
Goals:
Students will:
Student Outcomes:
Instructor: P. Rogaway
Prepared By: P. Rogaway (May 2006)
Overlap Statement:
ECS 60 is the gateway to almost all upper-division computer science courses,
and as such does not overlap with them except for brief review. There
is no overlap with other courses.