CS A275: Data Structures in Java

Course Outline of Record
Item	Value
Eff Term	Fall 2026
Curriculum Committee Approval Date	11/12/2025
Top Code	070600 - Computer Science (Transfer)
Units	4 Total Units (Lecture Units 3.5; Lab/Other Units 0.5)
Hours	90 Total Hours (Lecture Hours 63; Lab Hours 27)
Total Outside of Class Hours	126
Total Student Learning Hours	216
Course Credit Status	Credit: Degree Applicable (D)
Material Fee	No
Basic Skills	Not Basic Skills (N)
Repeatable	No
Open Entry/Open Exit	No
Grading Policy	Standard Letter (S), Pass/No Pass (B)
Associate Arts Local General Education (GE)	Area 2 Mathematical Concepts and Quantitative Reasoning (OMTH)
Associate Science Local General Education (GE)	Area 2 Mathematical Concepts and Quantitative Reasoning (OMTH)

Course Description

This course covers object-oriented programming, data abstraction, and algorithm analysis, with emphasis on data structures such as linked lists, stacks, queues, trees, and graphs. Students learn both their direct implementation and their application using Java Collections. Algorithms include searching, sorting, pattern matching, tree traversals, and balancing. It is intended for students pursuing a degree in Computer Science or a related field and is required for the state Computer Science AS-Transfer (AST) degree. PREREQUISITE: CS A170. Transfer Credit: CSU; UC.

Course Level Student Learning Outcome(s)

Write programs that implement and apply core data structures (linked lists, array lists, stacks, queues, trees, and graphs) through both direct implementation and appropriate use of Java Collections with generics.
Demonstrate proficiency with recursive methods by designing and coding recursive solutions to a variety of programming problems, including traversal and divide-and-conquer approaches.
Analyze and evaluate fundamental algorithms for searching, sorting (e.g., merge sort, quicksort, binary search), and structural operations, with emphasis on efficiency.

Course Objectives

Analyze algorithm efficiency using mathematical foundations, recursion, iteration, and asymptotic notation.
Apply object-oriented design principles to implement abstract data types and data structure libraries in Java.
Design, implement, and evaluate data structures including lists, stacks, queues, sets, maps, trees, heaps, and hash tables, and assess trade-offs among implementations.
Implement and evaluate algorithms for sorting, searching, and hashing, and explain their efficiency and applications.
Develop and apply graph algorithms (DFS, BFS, shortest paths, spanning trees, topological sorting) to solve computational problems.
Demonstrate critical thinking and problem-solving by selecting and justifying appropriate algorithms and data structures to create efficient, modular, and reusable software.

Lecture Content

Mathematics Review
1. Algebraic foundations for algorithms
2. Logarithms and exponent rules
3. Growth rates and asymptotics
Programming and Memory Concepts Review
1. OOP concepts: encapsulation, inheritance, polymorphism, class hierarchies
2. Using classes and interfaces to define abstract data types
3. Collection classes and iteration protocols in the Java Collections Framework
4. Memory models: primitive types, strings, stack allocation, heap allocation, pointers and references
5. Basic software design principles: modularity, abstraction, style, and debugging
Algorithm Analysis
1. Running time calculations
2. Big-O notation and growth rates
3. Comparing iterative and recursive solutions
4. Amortized analysis
5. Maximum subsequence sum problem
Lists and Abstract Data Types
1. ADTs
2. Lists in the Java collections API
3. Records (structs, tuples)
4. Linked lists (singly, circular, doubly)
5. Iterators
6. Nested and inner classes
Stacks
1. The stack ADT
2. Interface for stack classes
3. Stack representations (sequential and linked list)
4. Role of stacks in recursion
5. Applications: balanced parentheses and postfix evaluation
Queues
1. The queue ADT
2. Interface for queue classes
3. Regular, circular, and priority queues
4. Queue representations (sequential and linked list)
5. Applications in operating systems
6. Simulations
Trees
1. Implementation of a tree data structure
2. Tree traversals
3. Binary search trees
4. Tree balancing operations
5. AVL trees
6. Splay trees
7. 2–3 trees
8. B-trees
9. Red-black trees
Sets and Maps
1. Sets and maps as ADTs
2. TreeSet and TreeMap implementations
Hashing
1. Hash functions and efficiency considerations
2. Separate chaining
3. Open addressing
4. Linear probing
5. Quadratic probing
6. Double hashing
7. Rehashing
8. Hash tables in the API
Priority Queues (Heaps)
1. Binary heap
2. Applications of priority queues
3. The selection problem
4. Event simulation
5. Priority queues in the API
Sorting
1. Insertion sort
2. Shellsort
3. Heapsort
4. Mergesort
5. Quicksort
6. Radix sort
7. Decision trees for sorting
The Disjoint Set Class
1. Equivalence relations
2. The dynamic equivalence problem
3. Disjoint set data structures
Graph Algorithms
1. Graph terminology and representations
2. Graph ADT and implementations
3. Depth-first search (DFS)
4. Breadth-first search (BFS)
5. Topological sort
6. Task scheduling (applications of topological sorting in DAGs)
7. Shortest-path algorithms (unweighted, Dijkstra’s)
8. Minimum spanning trees (Prim’s, Kruskal’s)
9. Network flow problems
10. Directed, undirected, and acyclic graphs
11. Connectivity and biconnectivity
12. Euler circuits
13. Applications of graph algorithms
Algorithm Design Techniques
1. Divide and conquer algorithms
2. Greedy algorithms (scheduling, Huffman coding, bin packing)
3. Backtracking
4. Randomized algorithms
5. Random number generators
6. Skip lists

Lab Content

Lists and ADTs: Implementing lists, records, and iterators; comparing array-based and linked representations.
Stacks: Expression evaluation, recursion support, and practical applications.
Queues: FIFO structures, circular and priority queues, and basic simulations.
Trees: Implementing and traversing binary trees, search trees, and balanced trees.
Sets and Maps: Building sets/maps, frequency counting, and lookups using standard libraries or custom implementations.
Hashing: Hash table construction, collision handling, and efficiency experiments.
Priority Queues (Heaps): Heap operations and applied scheduling problems.
Sorting: Implementing and comparing algorithms across input types.
Graph Algorithms: Representing graphs as an adjacency list and adjacency matrix, performing traversals, and applying classic algorithms (shortest path, MST, topological sort).

Method(s) of Instruction

Lecture (02)
DE Live Online Lecture (02S)
DE Online Lecture (02X)
Lab (04)
DE Live Online Lab (04S)
DE Online Lab (04X)

Instructional Techniques

Lecture, demonstration, and in-class programming exercises.

Reading Assignments

Students will spend a minimum of 4 hours per week reading the textbook and/or other reading material assigned. Students will be expected to follow along with the exercises in the reading material.

Writing Assignments

Students will spend a minimum of 6 hours per week writing code.

Out-of-class Assignments

Students will spend a minimum of 6 hours per week completing weekly programming assignments.

Study Non-Contact Hours Recommended

126

Methods of Student Evaluation

Midterm Exam
Final Exam
Short Quizzes
Written Assignments
Projects (Individual/Group)
Problem Solving Exercises
Skills Demonstration

Demonstration of Critical Thinking

Tests and quizzes; coding assignments; programming projects; discussion/reflection.

Required Writing, Problem Solving, Skills Demonstration

Written exams; coding assignments; lab exercises; programming projects; short technical reports.

Resources Subscreen

Textbook: Dan S. Myers. Data Structures and Algorithms in Java. Cambridge University Press (2024).

Eligible Discipline(s)

Computer science: Master’s degree in computer science or computer engineering OR bachelor’s degree in either of the above AND master’s degree in mathematics, cybernetics, business administration, accounting or engineering OR bachelor’s degree in engineering AND master’s degree in cybernetics, engineering mathematics, or business administration OR bachelor’s degree in mathematics AND master’s degree in cybernetics, engineering mathematics, or business administration OR bachelor’s degree in any of the above AND a master’s degree in information science, computer information systems, or information systems OR the equivalent. Note: Courses in the use of computer programs for application to a particular discipline may be classified, for the minimum qualification purposes, under the discipline of the application. Master's degree required.

Academic Catalogs