Computer Science

ECS 60 Data Structures and Programming

ECS 60 Data Structures and Programming (4 units)

Format
Lecture: 3 hours
Discussion: 1 hour

Prerequisites: Course 40 (C++ and UNIX) with a grade of C- or better

Catalog Description:
Design and analysis of data structures for a variety of applications. Trees, heaps, searching, sorting, hashing, graphs. Extensive programming.

Summary of course contents

A systematic study of data structures, including stacks, queues, lists, skip lists, trees, binary search 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.

Goals: Students will: (1) learn to think clearly about and solve complex and poorly-defined programming tasks, and (2) 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) write working code.

Illustrative reading

  • M. Weiss, Data Structures and Algorithms in C++, 3rd edition,Addison Wesley, 2006
  • E. Horowitz, S. Sahni, D. Mehta. Fundamentals of Data Structures in C++, Second Edition , Silicon Press, 2006

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

GE3
Science & Engineering
Quantitative Literacy

Overlap: 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.

Instructors: Staff

History: 2012.10.19 (M. Neff): Added an alternative textbook, dropped mention of excluding 110 and rephrased point d). Prior course description by P. Rogaway, May 2006

Outcomes

1 X an ability to apply knowledge of mathematics, science, computing, and engineering
2   an ability to design and conduct experiments, as well as to analyze and interpret data
3 X an ability to design, implement, and evaluate a system, process, component, or program to meet desired needs, within realistic constraints such as economic, environmental, social, political, ethical, health and safety, manufacturability, and sustainability
4   an ability to function on multi-disciplinary teams
5 X an ability to identify, formulate, and solve computer science and engineering problems  and define the computing requirements appropriate to their solutions
6   an understanding of professional, ethical, legal, security and social issues and responsibilities
7   an ability to communicate effectively with a range of audiences
8   the broad education necessary to understand the impact of computer science and engineering solutions in a global and societal context
9 X a recognition of the need for, and an ability to engage in life-long learning
10   knowledge of contemporary issues
11 X an ability to use current techniques, skills, and tools necessary for computing and engineering practice
12 X an ability to apply mathematical foundations, algorithmic principles, and computer science and engineering theory in the modeling and design of computer-based systems in a way that demonstrates comprehension of the tradeoffs involved in design choices
13 X an ability to apply design and development principles in the construction of software systems or computer systems of varying complexity
border