Back to course 'CS201: Elementary Data Structures'

Topic outline

  • Unit 8: Hash Tables, Graphs, and Trees

    Collapse all Expand all

    This unit will identify various problems that computer scientists encounter when using array indexes and present Hash Tables as a solution. Students will learn about different Hash Tables categories, identifying their respective performance efficiencies. The unit will conclude with an introduction to graphs and special graph types known as trees and binary trees. We will learn how to implement these new Data Structures, discuss operations that accompany them, and identify different ways of traversing, searching, and sorting them.

    Completing this unit should take approximately 9 hours.

    • Upon successful completion of this unit, you will be able to:

      • demonstrate effective hash tables.
        • define hashtable and hash function.
        • describe the attributes of good hash functions.
        • describe several common hash functions.
        • apply hash tables and hash functions for insertion, deletion, and value access within a specific application.
      • demonstrate effective graphs.
        • define graph.
        • state the components of a graph.
        • describe the two principal graph traversal paradigms.
        • demonstrate the use of graphs as a solution to a particular application requirement.
        • know the difference between directed and undirected graph.
        • define spanning tree.
        • explain means of generating spanning trees.
        • define graph cycle.
      • demonstrate effective trees.
        • state the difference between trees and graphs.
        • define the basic components of a tree: root, leaf, branch, node, level.
        • know the difference between binary and nonbinary trees.
        • apply trees to solve specific application requirements.

    • 8.1: Hash Tables

      • page icon
        Hashing with Chaining Page
        Students must
        Mark as done

        This lecture introduces the concept of key/value pairs and how to search for them via hash functions. Chaining is used to handle collisions, which are when multiple values share the same key.

      • page icon
        Table Doubling and Karp-Rabin Page
        Students must
        Mark as done

        This lecture expands upon the previous one to introduce the possibilities of running out of space in the hash table or of having chains that are too long. In those cases, we would want to increase the size of the hash table; this lecture discusses how to do that effectively.

      • page icon
        Open Addressing and Cryptographic Hashing Page
        Students must
        Mark as done

        Watch this lecture, which foregoes chaining as a means of handling collisions and uses table-probing instead.

      • resource icon
        Hashing File
        Students must
        Mark as done

        Read this section on hashing, which presents a different perspective than the lectures above. This section uses C/C++ syntax.

    • 8.2: Graphs

      • resource icon
        Graphs File
        Students must
        Mark as done

        In computer science, the term "graph" refers to a set of vertices (points or nodes) and of edges (lines) that connect the vertices. The creation and traversal of graphs is an important topic when learning to solve complex problems that involve numerous relationships. Read this chapter for an excellent discussion on graphs and graph traversal.

      • resource icon
        Graphs and Network Flows File
        Students must
        Mark as done

        Review these slides, which discuss different graph representations and the efficiency of various representations.

      • page icon
        Finding Non-Cyclical Paths between Arbitrary Pairs of Nodes Page
        Students must
        Mark as done

        This article explains how to find all non-cyclical paths in a graph. Creating a traversal that visits nodes only once while still reaching the goal is a part of creating efficient solutions.

      • 8.2.1: Graph Searches

        • page icon
          C Program for Depth-First Search in a Graph Page
          Students must
          Mark as done

          There are many ways to traverse a graph; this article focuses on depth-first. This approach seeks a solution by going to the nodes furthest from the starting point.

        • page icon
          Breadth-First Search Page
          Students must
          Mark as done

          Another way to traverse a graph is to seek solutions starting at the closest nodes. This article explains how that is accomplished.

      • 8.2.2: Finding Lowest-Cost Paths

        • page icon
          Dijkstra's Algorithm Page
          Students must
          Mark as done

          Getting from one node in a graph to another while expending the least cost is important in many domains. This article discusses Dijkstra's algorithm and its implementation.

        • page icon
          Bellman's Algorithm Page
          Students must
          Mark as done

          An alternative approach to path finding is Bellman's algorithm. This page explains that approach and its implementation.

      • 8.2.3: Finding a Minimum Spanning Tree

        • page icon
          Minimum Spanning Trees – Kruskal's Algorithm Page
          Students must
          Mark as done

          For a graph's vertices (nodes) and weighted edges connecting the vertices, a minimum spanning tree contains only the minimum number of edges connecting all vertices while having the minimum total weight when compared to all sets of edges that connect all vertices. Note that there may be more than one set of edges that has the minimum sum of weights. This article explains Kruskal's method of obtaining a minimum spanning tree.

        • page icon
          Minimum Spanning Trees – Prim's Algorithm Page
          Students must
          Mark as done

          Prim created another popular approach to creating a minimum spanning tree. Since there is an infinity of potential application requirements and situations, there is never any one best approach in computer science, regardless of any academic snobbery you may encounter. Your ability to solve problems depends on your creativity, objectivity, and flexibility. Do not be trapped by an attempt to force-fit someone's favorite tool to all situations.

    • 8.3: Trees

      • page icon
        Trees Page
        Students must
        Mark as done

        Trees are a special case of graph, where the graph's nodes do not have multiple references. Tree traversal is only in one direction, downward, from root (top) to leaves (bottom). Read this page for basic definitions and illustrations.

      • resource icon
        Binary Trees File
        Students must
        Mark as done

        Most discussion about trees concerns binary trees, whose nodes have no more than two branches. Read this chapter, which offers background and practical applications for binary trees.

      • resource icon
        Non-Binary Trees File
        Students must
        Mark as done

        Read this chapter, which extends the discussion on binary trees to those trees whose nodes have more than just two branches.

    • Unit 8 Assessment

      • quiz icon
        Unit 8 Assessment Quiz
        Students must
        View
        Receive a grade

        Take this assessment to see how well you understood this unit.

        • This assessment does not count towards your grade. It is just for practice!
        • You will see the correct answers when you submit your answers. Use this to help you study for the final exam!
        • You can take this assessment as many times as you want, whenever you want.