Lower Division

Summary of Course Content

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:

• 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

• 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

GE3
Science & Engineering

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

Overlap
ECS 36C/60 and ECS 32B both cover data structures. 

Instructors
Staff

Outcomes

Summary of Course Contents

1. Object-Oriented Programming and the C++ Language.
   1. Object-oriented design and implementation, polymorphism, operator overloading, encapsulation, derivation, exceptions.
2. Programming in C
   1. Basic syntax and difference of C and other languages, including Python, and semantic differences of C with C++
   2. Data types: single and multidimensional arrays, character strings, structs.
   3. Use of system files such as library and “include” files
   4. Pointers and dynamic memory allocation.
   5. Functions: declaration and calls, & and * operators, parameters, function call stacks.
   6. Function pointers and inversion of control
3. Software Engineering & Tools
   1. Integrated Development Environments
   2. Debugging techniques, especially using UNIX debugging aids such as gdb/ddd.
   3. Version Control
   4. Unit Testing (e.g. GoogleTest)
   5. Program development using third party libraries, and use of the UNIX “make” program to organize them.
   6. Function pointers and inversion of control
4. Advanced Programming Concepts in C++
   1. Singly-and doubly-linked lists, recursion, and, if time permits, one or more topics chosen from: binary trees, stacks, queues
   2. Templates and the Standard Template Library
   3. Modern C++

Illustrative Reading
Stanley Lippman, Josee Lajoie, and Barbara Moo: C++ Primer, 5th ed., Addison-Wesley, 2013. 

GE3
Science & Engineering

Overlap
ECS 36B/40 and ECS 34 both cover object-oriented programming. 

Summary of Course Content

• The UNIX Environment
  • Review of basic UNIX environment concepts (e.g. processes/job control, file system, utilities, etc.)
  • Shell scripts
• Software Engineering & Tools
  • Debugging techniques using aids such as gdb/ddd.
  • Review of software engineering tools (e.g. make, git, etc.)
  • Unit Testing (e.g. Google Test)
  • Program development using third party libraries.
  • Other Tools (e.g. IDEs, ssh clients, linters, etc.).
• Programming in C
  • Basic syntax differences of C other languages, including Python
  • Data structures: single and multidimensional arrays; character strings; structs Use of system files such as library and “include” files
  • Pointers and dynamic memory allocation
  • Function pointers and inversion of control.
• Object-Oriented Programming in C++
  • Object-oriented design and implementation, polymorphism, operator overloading, encapsulation, derivation
  • Modular programming: programs composed of multiple C++ files and headers, overview of the
  • compilation/linking sequence
  • Pointer manipulation including dynamic memory allocation
  • Implementation of data structures (e.g. trees, graphs, etc.)
  • Templates and the Standard Template Library
  • Modern C++ (e.g. C++11, C++14, C++17, etc.)
• Analysis of Graph Algorithms
  • Critical path analysis, depth-first search, shortest path, minimum spanning tree, and network flow

Illustrative Reading

S. Lippman, J. Lajoie, and B. Moo, C++ Primer Fifth Edition, Addison Wesley, 2013.

W. Shotts, The Linux Command Line 2nd Edition, No Starch Press, 2019.

GE3
Science & Engineering

Overlap
This course is a non-major analog of ECS 036B and will overlap significantly in concepts. ECS 34 introduces UNIX and analysis of graph algorithms, which is not covered in ECS 036B.

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

• Introduction: the design of a computer, steps in solving a problem using a computer
• Algorithms: general concept, development of efficient algorithms
• Programming in Python
  • Scalar data types, concept of data type, standard and user-defined scalar types
  • Simple statements, arithmetic and boolean expressions, assignment statements, simple input and output statements (including file I/O)
  • Flow of control, repetitive statements, conditional statements
  • Data structures: lists, strings
  • Functions: general concept; declaration and calls; parameters
  • Classes
  • Use of an Integrated Development Environment  (IDE)

Illlustrative Reading
John Zelle, Python Programming: An Introduction to Computer Science, Addison-Wesley, 2010 

GE3
Science & Engineering

Overlap
This course overlaps in the introduction of basic programming concepts with ECS 12, ECS 15, ECS 30, ECS 36A, and Engineering 6. It covers Python programming in much greater depth than ECS 15. ECS 32A does not cover topics such as memory management, pointers, and arrays, which are covered in the context of C programming in ECS 30. ECS 32A does not cover topics such as the UNIX environment that are coved in ECS 36A. Engineering 6 covers programming in MATLAB, a specialized language for mathematical data analysis, and ECS 12 covers programming in PROCESSNG, a specialized language for media programming. ECS 32A covers general-purpose programming and is appropriate for all majors. 

• Propositional and first-order logic
• Elementary set theory.
• Functions, relations, and equivalence relations.
• Induction and recursion. Inductive definitions. Examples of induction taken from domains it is not obvious what one is inducting on.
• The pigeonhole principle.
• Asymptotic notation: O, W, Q.
• Derivation and solution of recurrence relations. Divide and conquer relations. Solutions through expansion and proofs by induction.
• Combinatorics and counting. Permutations, combinations. Non-trivial counting problems.
• Discrete probability
• Graphs and trees. Terminology. Eulerian and Hamiltonian graphs. Graph colorings. Basic properties of trees.

Goals
Students will: (1) learn fundamental ideas and techniques from discrete mathematics; (2) improve their ability to write concise and rigorous proofs; (3) improve their ability to understand mathematical definitions and proofs; and (4) enhance their general mathematical sophistication.

Illustrative reading

• K. Rosen, Discrete Mathematics and Its Applications, 7th edition, McGraw-Hill, 2011.
• M. Lipson, Schaum’s Outline of Discrete Mathematics, revised 3rd edition, 2009.
• D. Velleman, How to Prove it: A Structured Approach.  Cambridge University Press, 1994.

ABET Category Content
Engineering Science: 4 units
Engineering Design: 0 unit

Goals
Students will:

• Learn fundamental techniques in discrete mathematics for application to computer science
• Learn proof methods to transform intuition into proofs and know the distinction between proof and opinion
• Enhance their general mathematical sophistication in order to deal with and create complex and convincing arguments

GE3
Science & Engineering
Quantitative Literacy

Overlap
The course overlaps with Math 108 (Introduction to Abstract Mathematics) but focusses more on problems and techniques of utility in computer science. The course includes topics like asymptotic notation, graphs, and trees, which Math 108 does not include, while it omits topics like cardinal numbers, which Math 108 does include. ECS 20 is a fundamental, preparatory course for upper-division ECS courses.

Outcomes

I. Programming Fundamentals

• Variables, objects
• Conditionals, loops
• Functions
• Arrays and simple data structures
• Drawing primitives: lines, curves, polygons
• Basic program design

II. Going Digital: Representing Media in the Computer

• Signals
• Analog vs. Digital
• Sampling, filtering, discretization, sampling theorem
• Vector vs. Raster graphics
• Sound, images, movies
• Storage and Transmission
• Compression, Formats, Codecs

III. Computational Thinking

• How computer scientists analyze and solve problems
• Trends in computation

IV. Interaction

• Various forms of input (mice, sensors, depth cameras, etc.)
• Programming for interaction
• Event processing and callback functions

V. Time-Based Media

• Sound
• Animation

VI. Other Topics (time permitting)

• Games
• Computational photography
• Digital forgery
• Fonts

Goals
Media computation involves understanding both how media are represented in the computer and how they are manipulated and generated programmatically. This course introduces students who may have no background in programming to simple programs with clear graphical output, written in Processing. Processing is a computer language designed for artists that provides a simplified yet powerful interface. By first manipulating sample programs, students learn the connection between the commands and the generated output. They will then move towards developing their own programs for manipulating and generating media. Students will also study how media – images, sound and movies – are represented, stored and transmitted in/by computers. This gives students a solid basis for understanding digital media. More generally, it introduces them to how computational processes operate.

Illustrative reading

• Getting Started with Processing. Casey Reas and Ben Fry, O’Reilly Media, 2010.
• Processing: A Programming Handbook for Visual Designers and Artists, Casey Reas and Ben Fry, MIT Press, 2007.
• Learning Processing: A Beginner’s Guide to Programming Images, Animation, and Interaction, Daniel Shiffman, Morgan Kaufmann, 2008.
• Processing for Visual Artists: How to Create Expressive Images and Interactive Art, Andrew S. Glassner, A K Peters, 2010.

GE3
Arts & Humanities
Science & Engineering
Visual Literacy

Overlap
This course overlaps in the introduction of basic programming concepts with ECS 10, ECS 15, ECS 30, and Engineering 6, but uniquely introduces this material through the perspective of digital media. ECS 30 assumes previous programming experience and ECS 12 does not. ECS 12 also offers substantial novel content on digital media.

Summary of Course Content:

Programming fundamentals in modern C++ ○ Program structure, compilation, and execution 

• Built-in scalar types and type system concepts  
• Expressions, assignment, and basic input/output 
• Control flow: conditionals and loops 
• Functions, parameters, return values, and scope 
• Basic Standard Library containers  
• Introduction to structures and simple classes  
• References and pointers  
• Memory and resource management
• Interaction with files

Algorithmic problem solving 

• Designing small algorithms from specifications  
• Reasoning about correctness and efficiency  
• Introduction to linear data structures and recursion

Basic UNIX environment 

• Navigating the filesystem 
• Compiling and running programs from the terminal 
• Using basic command-line tools, redirection, and pipes

Software engineering practices  

• Debugging with tools such as GDB 
• Basic build system such as Makefile 
• Writing clear, readable programs  
• Testing and incremental development 
• Using standard libraries effectively 

Illustrative Reading: 

• Stroustrup, Bjarne, Programming: Principles and Practice Using C++, 3rd Edition, Addison-Wesley, 2024. 
• Shotts, William, The Linux Command Line: A Complete Introduction, No Starch Press, 2026.

Potential Course Overlap:

ECS 32A and ECS 36A/ECS 30 cover programming, but in ECS 36A it is covered more quickly and larger programs are written. ECS 36A also introduces UNIX.