ECS 110 Data Structures and Programming (4) I,II,III
Lecture: 3 hours
Discussion: 1 hour
Prerequisites: Courses ECS 20, ECS 40 (C++ and UNIX); and a grade of C- or better in each course
Grading: Letter; based on the programs (4 @ 10% each), one midterm (20%), 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:
Analysis of algorithms. Strings. Stacks. Queues. Trees. Tree traversals.
Binary trees. Expression trees. Binary search trees. Amortized analysis.
Hashing. Universal hashing. Heaps. Sorting algorithms. Graphs. Depth-first
Search. Minimum spanning trees. Shortest paths. Union/Find data structure.
Splay trees. Digital search trees. Tries. Huffman codes. Branch-and-Bound.
If time permits, any of the following: Skip lists, B-trees, Fibonacci
heaps.
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:
- learn to think clearly about and solve complex and poorly-defined programming tasks
- be able to (a) find appropriate abstractions to solve a complex problem, (b) choose appropriate data structures and algorithms, (c) analyze simple algorithms and discuss tradeoffs among data structures, (d) get it all working
Program Outcomes:
- The ability to apply knowledge of basic science, mathematics and engineering principles to solve computing and information processing problems
- The ability to write correct and good programs
- The ability to understand the tradeoffs in the design of hardware systems, software systems, processes and components
- The ability to construct appropriate abstractions to manage complexity and to think creatively about new problems
- The ability to acquire the foundations to be a life-long learner
Instructor: P. Rogaway
Prepared By: P. Rogaway (May 2006)
Overlap Statement:
ECS 110 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.
5/06