CSCE 221

Data Structures & Algorithms

  1. Data Structures
    •  Stacks
    •  Queues
    •  Linked lists
    •  The tree abstract data type and data structures for representing trees
    •  Properties of binary trees
    •  Binary search trees
    •  AVL trees
    •  Red‐black trees
    •  The priority queue abstract data type
    •  The heap data structure
    •  Hash tables
    •  Data structure of graphs
    •  The edge list
    •  The adjacency list
    •  The adjacency matrix
  2. Algorithms
    •  Sorting
    •  Merge‐sort
    •  Quick‐sort
    •  The Huffman coding algorithm
    •  Solving the longest common subsequence problem using dynamic programming
    •  Basic algorithms on trees
    •  Pre‐order traversal
    •  Post‐order traversal
    •  Graph traversal
    •  Depth‐first search
    •  Breadth‐first search
    •  Topological order and sorting of directed acyclic graphs
    •  Shortest paths: Dijkstra’s algorithm
    •  Minimum spanning trees
    •  Kruskal’s algorithm
    •  Prim’s algorithm
  3. Complexity Analysis
    •  Asymptotic notations: the “big‐Oh” notation
    • Asymptotic analysis using the big‐Oh notation