Skip to Main Content

Data Structures

Computer Science Department

Lectures

Topics

Learning Objectives

Resources

  • Memory representation (stack and heap)

  • Objects

  • Arrays

  • Union Find
  • Complexity Analysis
  • (1.1A1.1B) Implement and analyze Java code to manipulate 1D and 2D arrays.
  • (1.2A, 1.2B) Describe and illustrate memory representation and allocation involving-1D and 2D array implementations in Java.
  • (1.3) Explain algorithmic efficiency as it relates to speed and space consumption.
  • (1.4) Categorize algorithms according to their Big O complexity.
  • (1.5) Compare and contrast algorithmic efficiencies: Linear, Quadratic, Logarithmic, Linearithmic.
  • (1.6) Explain what is meant by  “Garbage Collection” as it relates to Java and list one advantage and one disadvantage of its implementation.
  • (1.7) Use debugging tools to step through code in order to identify errors at various stages of program development.
  • (1.8) Describe the dynamic connectivity problem.
  • (1.9A, 1.9B) Describe the quick-find algorithm and its analysis.
  • (1.10A, 1.10B) Describe the quick-union algorithm and its analysis.
  • (1.11A, 1.11B) Describe the weighted quick-union and its analysis.
  • (1.12) Compare Big-O efficiencies of quick-find,  quick-union and, weighted quick-union.
  • (1.13) List 3 union-find applications.
  • Stacks
  • Queues
  • (2.1) (2.1A)(2.1B)(2.1C)(2.1D)(2.1E)(2.1F)(2.1G)Implement stacks, and queues using arrays and linked lists.
  • (2.2) Describe and illustrate memory representation and allocation when implementing stacks/queues using arrays or linked lists.
  • (2.3) Implement common methods for stacks that include isEmpty, push, pop, isFull, peek, and size.
  • (2.4) Implement common methods for queues including enqueue, dequeue, isEmpty, isFull, peek, and size.
  • (2.5) (2.5A)(2.5B)Explain and  implement a method resize that will increase/decrease capacity of an array.
  • (2.6) Implement stacks and queues using generics.
  • (2.7) Discuss the advantages and disadvantages of linked list implementation of stacks/queues.
  • (2.8) Discuss the advantages and disadvantages of an array implementation of stacks/queues.
  • (2.9) Compare Big-O efficiencies of stack and queue operations using arrays and linked lists.
  • (2.10) List examples where array implementations of stacks/queues is more appropriate than linked-list implementations and vice-versa.
  • Circular Linked List
  • Doubly Linked List
  • (3.1) Describe and illustrate memory representation and allocation when implementing circular-  and doubly- linked lists.
  • (3.2) Implement common methods on circular- and doubly- linked lists including, but not limited to, insert, delete, update, traverse.
  • (3.3) Given a problem statement, design, develop, debug, and test a Java program that uses an appropriate data structure(s).
  • (3.4) List the advantages and disadvantages of using circular linked lists and doubly-linked lists.
  • (3.5) Give at least one application where it is more appropriate to use a circular linked list than it is to use any other data structure. Justify your choice.
  • (3.6) Give at least one application where it is more appropriate to use a doubly-linked list than it is to use any other data structure. Justify your choice.

Binary Search Algorithm

  • (4.1) Design and implement a recursive binary search method.
  • (4.2) Explain and illustrate the call stack developed in a recursive binary search.
  • (4.3) Illustrate lower bound analysis of binary search with decision trees. 
  • (4.4) Explain the best, worst, and average cases for the binary search.
  •  

Binary Search Trees

  • (5.1) Define a symbol table and discuss the methods included in the ordered symbol table API.
  • (5.2) Create and implement a BST.
  • (5.3) Explain, with code examples, the algorithms for inserting, deleting, and searching for nodes in a BST.
  • (5.4) Implement code to find the smallest/largest element in a BST.
  • (5.5) Identify the best case/worst case for insertions to a BST.
  • (5.6) Discuss the pros and cons of using BSTs
  • (5.7) Illustrate resulting BSTs if given data elements to insert or delete. 
  • (5.8) Illustrate inorder, preorder, and postorder traversals of BSTs and discuss applications appropriate for each.
  • (5.9) Compute the floor, ceiling, and rank of a key in a  BST.
  • (5.10) List at least three real world applications that would best be solved using a BST rather than other data structures studied so far. Explain why.
  • (5.11) List at least three real world applications that would best be solved using a data structure other than a BST. Explain why.

Balanced Search Trees

  • (6.1) Explain what is meant by a balanced binary tree and why it is important.
  • (6.2) Illustrate and explain the structure of a 2-3 tree.
  • (6.3) Explain the insertion into a 2-3 tree and the invariants associated with it.
  • (6.4) Explain and implement search as it relates to red-black (RB) trees.
  • (6.5) Implement RB tree insert.
  • (6.6) Explain the guaranteed logarithmic performance for search and insert for RB trees.
  • (6.7) Explain the advantages of RB trees.
  • (6.8) Give conditions when implementing a RB tree is most appropriate.
  • (6.9) Explain the purpose of a B-tree and how it relates to, and differs from, a 2-3 tree.
  • (6.10) Illustrate and explain the structure of a B-tree.
  • (6.11) Explain how searching, inserting, and balancing takes place in a B-tree.

Priority Queues

  • (7.1) Explain the properties of a priority queue.
  • (7.2) Implement the operations of insert (swim), delete (sink), isEmpty.
  • (7.3) List at least 3 real world examples in which a priority queue would be the data structure of choice.
  • (7.4) Discuss the order and shape invariant checking for insert/delete.
  • (7.5) Given an array, illustrate how heapsort works by showing the state of the heap after each step, using both array and tree representations. 
  • (7.6) Analyze the time complexity of heapsort.

Hash Tables

  • (8.1) Explain the purpose of implementing a hash table.
  • (8.2) List and discuss at least three different techniques for calculating a hash function.
  • (8.3) Discuss the considerations when selecting a hash table size.
  • (8.4) Explain load factor and how it influences the decision to resize the hash table.
  • (8.5) Discuss the various techniques of array resizing (increase by 1, double the size).
  • (8.6) Describe by illustrations linear probing and chaining as collision resolution techniques.
  • (8.7) Discuss the consequences of adding and deleting elements when using  linear probing and chaining.
  • (8.8) Explain the tradeoffs between the different collision resolution techniques.
  • (8.9) Analyze hash tables that implement linear probing and chaining in the best case and worst-case scenarios.
  • (8.10) List at least two real-world applications for hash tables.

Undirected Graphs

(9A.1) Apply graph terminology to real word scenarios.
(9A.2) Describe the undirected graph API.
(9A.3) List two examples of real-world applications of weighted and non-weighted undirected graphs.
(9A.4) Illustrate at least two examples of undirected graphs and explain how the undirected graph API would be implemented using your illustrations.
(9A.5) Represent a graph with a two-dimensional adjacency matrix of Booleans.
(9A.6) Represent a graph with a vertex-indexed array of lists.
(9A.7) Implement typical graph processing code.
(9A.8) Analyze code segments to compare the growth of running times between a two-dimensional adjacency matrix and a vertex-indexed array of lists graph representations.
(9A.9) Implement an undirected graph with a vertex-indexed array of lists
(9A.10) Explain, with an illustration, Depth-First Search (DFS) in an undirected graph.
(9A.11) Implement a recursive DFS for an undirected graph.
(9A.12) Explain, with an illustration, Breadth-First Search (BFS) in an undirected graph.
(9A.13) Implement BFS for an undirected graph.
(9A.14) List at least two real-world applications of DFS and BFS that might be implemented using an undirected graph.

Directed Graphs

  • (9B.1) Describe the directed graph API.
  • (9B.2) Correctly use and explain terminology related to directed graphs.
  • (9B.3) Explain the difference between directed graphs and undirected graphs.
  • (9B.4) List two examples of real-world applications of weighted and non-weighted directed graphs.
  • (9B.5) Explain and illustrate a directed graph and a directed cycle.
  • (9B.6) Implement a directed graph with a vertex-indexed array of lists.
  • (9B.7) Analyze code segments to determine the growth of running time of a directed graph that is implemented using a vertex-indexed array of lists.
  • (9B.8) Explain, with an illustration, Depth-First Search (DFS) in a directed graph.
  • (9B.9) Discuss the differences among pre-order, post-order, reverse post-order vertex orderings.
  • (9B.10) Explain, with an illustration, Breadth-First Search (BFS) in a directed graph.
  • (9B.11) List at least two real-world applications of directed graphs.
  • (9B.12) Explain the differences between a directed graph and a directed cycle.
  • (9B.13) Discuss the concept of reachability in directed graphs.
  • (9B.14) Given a directed graph, find the shortest path between one vertex and another.
  • (9B.15) Describe and illustrate a topological sort of a directed graph.
  1. Insertion Sort
  2. Selection Sort
  • (10A.1) Given an array of values, give a step-by-step illustration of executing the selection sort on the array. State the array contents after each pass of the sort.
  • (10A.2) Determine the best case and worst case Big-O analysis of the selection sort.
  • (10A.3) Given an array of values, give a step-by-step illustration of executing the insertion sort on the array. State the array contents after each pass of the sort.
  • (10A.4) Determine the best case and worst case Big-O analysis of the insertion sort.
  •  

Mergesort

  • (10B.1) Given an array of values, give a step-by-step illustration of executing the Mergesort sort on the array. State the array contents after each call to merge.
  • (10B.2) Determine the best case and worst case Big-O analysis of the Mergesort.

Quicksort

  • (10C.1) Given an array of values, give a step-by-step illustration of executing the Quicksort sort on the array.  State the array contents after each partition.
  • (10C.2) Determine the best case and worst case Big-O analysis of the Quicksort.
  • (10C.3) Explain the meanings of  “in place sort” and “stable sort”.
  • (10C.4) Indicate whether or not each sort (insertion, selection, merge, quick) is an “in place” sort.
  • (10C.5) Indicate whether or not each sort (insertion, selection, merge, quick) is a stable sort.
  • (10C.6) Explain the advantage of combining Insertion sort  with Quicksort (or Mergesort)  when sorting a large array.
  • (10C.7) Describe at least two ways  to “shuffle” items in an array.