ECS 032B: Introduction to Data Structures

Subject
ECS 032B
Title
Introduction to Data Structures
Status
Active
Units
4.0
Effective Term
2018 Fall Quarter
Learning Activities
Lecture - 3.0 hours
Discussion - 1.0 hours
Description
Design and analysis of data structures using Python; trees, heaps, searching, sorting, and graphs. No credit to students who completed ECS 036B, ECS 036C, ECS 040, or ECS 060. GE Prior to Fall 2011: SciEng. GE: SE.
Prerequisites
ECS 010 C- or better or ECS 030 C- or better or ECS 032A C- or better or ECS 036A C- or better
Credit Limitation
No credit to students who completed ECS 036B, ECS 036C, ECS 040, or ECS 060.
Enrollment Restrictions
Not open to Computer Science and Computer Science & Engineering majors

Summary of Course Content

  • Recursion
  • Theory: Complexity, algorithm analysis
  • Abstract Data Types
  • Stacks, queues, lists, trees, balanced binary search trees, priority queues, graphs
  • Analysis of Sorting Algorithms
  • Insertion sort, merge sort, heapsort, bucket sort, and radix sort

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

Illustrative Reading
Fundamentals of Python: Data Structures by Kenneth Lambert

  1. A Quick Course in Basic Python. 2. Basic Algorithms: Searching and Sorting. 3. Basic Data Structures: Arrays and Linked Structures. 4. Object-Oriented Design: Interfaces, Implementations, Polymorphism, and Inheritance. 5. An Overview of Collections. 6. Stacks and Queues. 7. Abstract Collections. 8. Lists. 9. Trees. 10. Sets and Dictionaries. 11. Graphs

Problem Solving with Algorithms and Data Structures Using Python, 2nd Edition by Bradley N. Miller, David L. Ranum

http://interactivepython.org/courselib/static/pythonds/index.html

  1. Review of Basic Python, 2. Analysis, 3. Basic Data Structures, 4. Recursion, 5. Sorting and Searching, 6. Trees and Tree Algorithms, 7. Graphs and Graph Algorithms

Data Structures and Algorithms with Python (Undergraduate Topics in Computer Science) by Kent D. Lee and Steve Hubbard

  1. Python Programming 101, 2. Computational Complexity, 3. Recursion, 4. Sequences (Sorts), 5 Sets and Maps, 6. Trees, 7. Graphs, 8. Membership Structures, 9. Heaps, 10. Balanced Binary Search Trees, 11. B-Trees, 12. Heuristic Search

GE3
Science & Engineering

Overlap
This course is a Non-Major version of ECS 36C and will overlap significantly in concepts. 

Instructors
Staff

Course Category

Lower Division