CS113: Data Structures and Algorithm Analysis

MiraCosta CS113 outline: available lessons, algorithm and data-structure implementation gaps, and differentiated Web project extensions for each college topic.

Source ownership follows CS112, CS113, CSA1, CSA2, then DS2. Week assignments remain in the shared CSA course plan. Articulation metadata identifies a curriculum connection, not earned credit or demonstrated mastery.

CS113 Instruction / Examples

This report follows MiraCosta's CS113 outline. Lessons are grouped by college topic, not by teaching week; a lesson can support several subtopics without becoming an additional assignment.

Teaching progression: Search and sort foundations are introduced early in CSA2 for AP preparation and Web project needs. Later DS2 work extends algorithm analysis and implementation. Week assignments remain in the shared CSA course plan; AP weeks review earlier work rather than introduce new assignments.

Differentiated depth: Advanced from-scratch CS113 implementations are opportunities for students ready to pursue those layers. Not every student is expected to complete every layer; DS2 ML/AI remains an alternative pathway.

Weeks and reference status come from current lesson metadata. Drafts are unfinished authoring work, not live assignments. Available examples and library usage do not establish implementation mastery or earned credit.

Mapped Java Reference lessons supplement this outline. Their original ownership and week assignments are unchanged; inclusion here does not add an assignment or claim articulation credit.

I. Object-oriented programming (OOP) design and algorithmic analysis

A. Computationally efficient coding through algorithms, pseudo-code, UML, and flow diagrams before coding

Available material: Java algorithm, abstraction, and program-design references complement calculator enactments, RPN pipelines, and sorting simulations for planning before implementation.

Strengthening / gap: Require a student-authored design artifact before coding. An enactment or supplied implementation alone does not demonstrate UML or pseudo-code design.

PBL observation or extension: Diagram a feature's data flow and algorithm, then trace one request through the planned steps.

B. Growth functions and Big O notation

Available material: Selection/insertion, merge sort, and sorting homework introduce growth rates. Java Informal Run-Time Analysis and Sorting Algorithms add statement counts and comparison-count runners; formal Big O is a college extension to those AP foundations.

Strengthening / gap: Strengthen explanations that connect code operations to a growth function rather than memorizing a Big O label.

PBL observation or extension: Count a feature's dominant operations and justify the resulting complexity.

C. Growth function comparison as the number of inputs increases

Available material: Search and sorting examples provide different growth rates. Java sorting runners compare operation counts on sorted and reversed inputs; advanced analysis has an authoring draft.

Strengthening / gap: Add reproducible comparisons across increasing input sizes, with operation counts and controlled data.

PBL observation or extension: Compare list scanning and map lookup for a growing project dataset; plot counts alongside timings.

D. Time complexity issues

Available material: Search, sort, and graph-search materials offer examples for discussing best/worst cases and algorithm trade-offs.

Strengthening / gap: Separate asymptotic analysis from measured runtime, including setup costs and input-order effects.

PBL observation or extension: Identify a slow lookup or ordering operation and explain whether an algorithm or data-structure change would help.

E. Testing - 1. Preparations for testing

Available material: RPN tracking and calculator examples expose intermediate states. Implementation drafts include evidence checklists to author.

Strengthening / gap: Add an explicit test plan, expected results, and invariants before students implement advanced layers.

PBL observation or extension: Define what must remain true after each queue, stack, or heap operation and plan tests before coding.

E. Testing - 2. Developing appropriate test data

Available material: Calculator examples supply expressions; sorting homework supplies a small array. Java sorting compares input orders, and recursive searching/sorting asks for predicted versus actual results with additional peer-test inputs.

Strengthening / gap: Expand beyond supplied examples to deterministic sorted, reverse-sorted, duplicate, and malformed inputs with known expected results.

PBL observation or extension: Create representative and adversarial datasets for the project's algorithm and explain why each test matters.

E. Testing - 3. Testing boundary conditions

Available material: Java recursion and recursive searching/sorting include base cases, empty and singleton inputs, and missing-target behavior. Hash-table, heap, and tree drafts provide contexts for further boundary checks.

Strengthening / gap: Extend the existing array/recursion boundary tests to empty structures, collisions, missing keys, and invalid heap/tree operations.

PBL observation or extension: Test an empty queue, a missing map key, and a graph with no path; verify useful failure behavior.

II. Data structures and collections

A. Stacks, heaps, queues, priority queues, and lists

Available material: RPN calculators and queue/deque lessons cover stack and queue behavior and library implementation choices. Heap and priority-queue implementation layers are drafted.

Strengthening / gap: Finish student-built heap operations and priority ordering. Using a library PriorityQueue does not demonstrate implementing a heap.

PBL observation or extension: Compare FIFO task handling with priority scheduling and explain the ordering invariant.

B. Linked lists, trees, binary trees, binary search trees, 2-3-4 trees, and skip lists

Available material: Queue/deque references discuss library LinkedList use. The tree implementation skeleton is available for authoring; from-scratch linked-list foundations are mapped in the CS112 report.

Strengthening / gap: Finish tree/BST insertion, traversal, and search. Dedicated 2-3-4 tree and skip-list lessons are still needed; graph lessons are not a substitute for tree implementation.

PBL observation or extension: Build a search index for project records and compare a BST with a linked-list scan.

C. Application and implementation approaches

Available material: RPN variants, tracking, and enactments show how stacks and queues participate in a complete expression-processing pipeline.

Strengthening / gap: Make the layers explicit: trace the existing example, use a collection API, then implement and test a selected structure from scratch.

PBL observation or extension: Extend the calculator or a project work queue and document where a library structure was used versus implemented.

III. Graphs, hash tables, sets, and maps

A. Networks and graphing strategies

Available material: Graph introductions, Java representations, BFS/DFS, and heuristic-search examples cover nodes, edges, adjacency structures, and path-finding strategies.

Strengthening / gap: Strengthen directed/weighted graph tests and the distinction between exact search and heuristic trade-offs.

PBL observation or extension: Represent dependencies or routes as a graph and compare traversal and path-finding strategies.

B. Hashing functions and resolving collisions

Available material: The search/HashMap lesson introduces hashing and lookup costs. A hash-table implementation draft addresses collisions and load factor.

Strengthening / gap: Finish a custom table with collision resolution and collision-heavy tests; library HashMap use alone is not implementation evidence.

PBL observation or extension: Build a small keyed lookup table and compare chaining with open addressing under deliberate collisions.

C. Implementation strategies

Available material: Set lessons provide uniqueness and collection operations; Java graph and search examples support adjacency representations and traversals.

Strengthening / gap: Require students to justify representation choices and test equality, duplicate handling, missing keys, and disconnected graphs.

PBL observation or extension: Use a set for deduplication, a map for keyed records, and a graph for relationships; explain each choice.

IV. Recursion

A. Divide and conquer technique

Available material: Java Recursion and Recursive Searching and Sorting cover base cases and shrinking search regions. Merge sort explicitly divides, recursively sorts, and combines subproblems; advanced drafts extend the comparison to quicksort.

Strengthening / gap: Require base-case reasoning, a recursive call trace, and evidence that merging preserves sorted order.

PBL observation or extension: Trace a merge sort on project records and explain the time and temporary-storage costs.

B. Dynamic programming

Available material: A differentiated dynamic-programming implementation skeleton exists.

Strengthening / gap: No completed dedicated lesson is available. Author overlapping subproblems, memoization, tabulation, and comparisons with the baseline algorithm.

PBL observation or extension: Choose a repeated-computation problem, cache subproblem results, and verify correctness and operation-count improvements.

A. Selection, insertion, shellsort, and bubble sorts

Available material: Selection/insertion instruction and simulations provide early AP-aligned practice. Java Sorting Algorithms adds complete pass traces and comparison-count runners. Sorting homework includes bubble sort as a choice.

Strengthening / gap: Complete dedicated bubble and Shell sort implementation/analysis layers and compare behavior on different input orders.

PBL observation or extension: Visualize sorting a small project dataset and count comparisons and moves.

B. Quicksort, merging and mergesort, heapsort, and radix sorts

Available material: Merge sort is a published lesson; sorting homework names quicksort. The advanced-sort draft plans quicksort, heapsort, and radix layers.

Strengthening / gap: Finish partitioning, heap reuse, and radix input constraints with correctness and performance comparisons.

PBL observation or extension: Select an ordering strategy for project records and justify it against the existing merge-sort baseline.

C. Performance characteristics of search routines

Available material: Java Linear Search Algorithms and Recursive Searching and Sorting add array search and recursive binary-search foundations to the linear/binary/hash and graph-search analysis examples.

Strengthening / gap: Make preconditions and trade-offs explicit: sorted input for binary search, hash distribution, and graph structure. Verify missing-target behavior.

PBL observation or extension: Compare linear, binary, and keyed lookup for a feature, then explain when graph traversal is the right model instead.

Lab Outline

Individual and group hands-on projects

Available material: Calculator enactments, RPN implementations, sorting visualizations, and graph exercises support, complement, and extend the lecture material and theory.

Strengthening / gap: Collect individual competence evidence alongside group project work. Advanced from-scratch CS113 layers are differentiated opportunities, not a claim that every student completes them.

PBL observation or extension: Choose a structure or algorithm layer, demonstrate its use or implementation in a project, and reflect on correctness and efficiency evidence.