CISC 235 Quiz 1 Study Notes

  • Quiz Information

    • Quiz 1 next Wednesday, 50 minutes
    • Closed book, room: Humphrey AUD, Jeffery 126

  • Data Structures

    • Organization of data in a computer, crucial for data manipulation.
    • Common structures: Arrays, Linked Lists, Trees, Graphs.

  • Algorithm and Data Structures

    • Algorithms are step-by-step procedures to perform operations on data structures.

  • Algorithm Analysis

    • Time Complexity: Time required for an algorithm to complete.
    • Space Complexity: Memory needed for an algorithm.

  • Time Complexity Measurement

    • Comparison of algorithms based on input size, e.g., $ ext{Algorithm A: } 5 imes N^2$, $ ext{Algorithm B: } 37,000 imes N$.

  • Asymptotic Behavior of Polynomials

    • Example: $p(n) = a3n^3 + a2n^2 + a1n + a0$ is in $ heta(n^3)$ for $a_3 > 0$.

  • Big-O Notation

    • Determines upper bounds of functions.
    • Example: Given $f(n) = 4n + 63 + 5n^2 + 3n ext{ log } n$, both tightest Big-O and Big-Omega = $n^2$.

  • Linked List Operations

    • Array vs Linked List operations (e.g., insert, delete, search) with associated complexities.

  • Tree Structures

    • Height of a node: edges from node to leaf.
    • Depth of a node: edges from node to the root.

  • Binary Search Trees (BST)

    • Properties: Left subtree < node < right subtree.
    • Insertion and deletion with O(log N) complexity.

  • AVL Trees

    • Self-balancing binary search trees via rotations.
    • Balanced with height $O(log N)$ to optimize search operations.