Software Engineering

Waterfall Model

• • Linear, sequential phases
• • Each phase must complete before next
• • No going back to previous phases
• + Simple, well-documented
• - Inflexible, late testing
• Best for: Well-defined, stable requirements

V-Model

• • Extension of Waterfall
• • Each dev phase has corresponding test phase
• • Testing planned in parallel with development
• + High discipline, early test planning
• - Still inflexible

Iterative/Incremental

• • Software built in increments
• • Each iteration adds functionality
• • Early partial implementation
• + Early feedback, risk reduction
• - Needs good planning

Spiral Model

• • Risk-driven approach
• • Four quadrants: Planning, Risk Analysis, Engineering, Evaluation
• • Each loop is a phase
• + Risk management, iterative
• - Complex, expensive

Array

• • Fixed size, contiguous memory
• • O(1) access by index
• • O(n) insertion/deletion (shifting)
• • Cache-friendly

Linked List

• • Dynamic size, non-contiguous
• • O(n) access (traversal needed)
• • O(1) insertion/deletion at known position
• • Types: Singly, Doubly, Circular

Stack (LIFO)

• • Last In, First Out
• • Operations: push(), pop(), peek()
• • O(1) for all operations
• • Uses: Undo, function calls, parsing

Queue (FIFO)

• • First In, First Out
• • Operations: enqueue(), dequeue()
• • O(1) for all operations
• • Uses: BFS, scheduling, buffers

Binary Tree

• • Each node has max 2 children
• • Terms: Root, leaf, height, depth
• • Traversals: Inorder, Preorder, Postorder, Level-order

Binary Search Tree (BST)

• • Left child < parent < right child
• • O(log n) average search/insert/delete
• • O(n) worst case (skewed tree)
• • Inorder gives sorted output

Heap

• • Complete binary tree
• • Max-heap: Parent ≥ children
• • Min-heap: Parent ≤ children
• • O(log n) insert, O(1) find-min/max
• • Uses: Priority queue, heap sort

Graph

• • Vertices (nodes) + Edges (connections)
• • Types: Directed/Undirected, Weighted/Unweighted
• • Representations: Adjacency Matrix, Adjacency List
• • Traversals: BFS, DFS

Linear Search

• • Check each element sequentially
• • Works on unsorted data
• • Time: O(n)
• • Space: O(1)

Binary Search

• • Requires sorted data
• • Divide and conquer
• • Compare middle, eliminate half
• • Time: O(log n)
• • Space: O(1) iterative, O(log n) recursive

BFS (Breadth-First Search)

• • Uses Queue
• • Level-by-level traversal
• • Finds shortest path (unweighted)
• • Time: O(V + E)

DFS (Depth-First Search)

• • Uses Stack (or recursion)
• • Go deep before backtracking
• • Good for: Cycle detection, topological sort
• • Time: O(V + E)

1. Encapsulation

Bundle data and methods that operate on data within a single unit (class).

• • Data hiding using access modifiers
• • Getters/setters for controlled access
• • Protects data integrity

2. Abstraction

Hide complex implementation, show only essential features.

• • Abstract classes (partial implementation)
• • Interfaces (contract, no implementation)
• • Focus on "what" not "how"

3. Inheritance

Create new classes based on existing classes (parent-child).

• • Code reuse
• • Types: Single, Multiple, Multilevel, Hierarchical
• • "is-a" relationship

4. Polymorphism

Same interface, different implementations.

• • Compile-time: Method overloading
• • Runtime: Method overriding
• • "One interface, many forms"

Black Box

• • Test without knowing internal code
• • Focus on inputs and outputs
• • Functional testing

White Box

• • Test with knowledge of internal code
• • Code coverage testing
• • Statement, branch, path coverage