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.1)(A)(B) Implement and analyze Java code to manipulate 1D and 2D arrays.
  • (1.2)(A)(B) 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.9)(A)(B) Describe the quick-find algorithm and its analysis.
  • (1.10)(A)(B) Describe the quick-union algorithm and its analysis.
  • (1.11)(A)(B) 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) (A)(B)(C)(D)(E)(F)(G)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) (A)(B)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 Trees

  • (4.1) Define a symbol table and discuss the methods included in the ordered symbol table API.
  • (4.2)(A)(B)(C)(D)(E) Explain the algorithms for inserting, deleting, and searching for nodes in a BST.
  • (4.3) Create and implement a BST.
  • (4.4) Implement code to find the smallest/largest element in a BST.
  • (4.5) Identify the best case/worst case for insertions to a BST.
  • (4.6) Discuss the pros and cons of using BSTs
  • (4.7) Illustrate resulting BSTs if given data elements to insert or delete. 
  • (4.8) Illustrate inorder, preorder, and postorder traversals of BSTs and discuss applications appropriate for each.
  • (4.9) Compute the floor, ceiling, and rank of a key in a  BST.
  • (4.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.
  • (4.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

  • (5.1) Explain what is meant by a balanced binary tree and why it is important.
  • (5.2)(A) (B) Illustrate and explain the structure of a 2-3 tree.
  • (5.3)(A) (B) Explain the insertion into a 2-3 tree and the invariants associated with it.
  • (5.4)(A)(B) Explain how 2-3 trees relate to left-leaning red-black (LLRB) trees.
  • (5.5) (A)(B)(C)(D)(E) Explain and implement LLRB tree insert.
  • (5.6) Explain the guaranteed logarithmic performance for search and insert for LLRB trees.
  • (5.7) Explain the advantages of LLRB trees.
  • (5.8) Give conditions when implementing a LLRB tree is most appropriate.
  • (5.9) Explain the purpose of a B-tree and how it relates to, and differs from, a 2-3 tree.
  • (5.10) Illustrate and explain the structure of a B-tree.
  • (5.11) Explain how searching, inserting, and balancing takes place in a B-tree.

Priority Queues

  • (6.1) Explain the properties of a priority queue.
  • (6.2) Explain the order and shape invariants of a binary heap.
  • (6.3) (A)(B)(C)(D)(E) Implement the operations of insert (swim), delete (sink), isEmpty.
  • (6.4) List at least 3 real world examples in which a priority queue would be the data structure of choice.
  • (6.5) Discuss the order and shape invariant checking for insert/delete.
  • (6.6) (A) (B) (C) Given an array, illustrate how heapsort works by showing the state of the heap after each step, using both array and tree representations. 
  • (6.7) Analyze the time complexity of heapsort.
  •  

Hash Tables

  • (7.1) Explain the purpose of implementing a hash table.
  • (7.2) List and discuss at least three different techniques for calculating a hash function.
  • (7.3) Discuss the considerations when selecting a hash table size.
  • (7.4) Explain load factor and how it influences the decision to resize the hash table.
  • (7.5) Discuss the various techniques of array resizing (increase by 1, double the size).
  • (7.6) Describe by illustrations linear probing and chaining as collision resolution techniques.
  • (7.7) Discuss the consequences of adding and deleting elements when using  linear probing and chaining.
  • (7.8) Explain the tradeoffs between the different collision resolution techniques.
  • (7.9) Analyze hash tables that implement linear probing and chaining in the best case and worst-case scenarios.
  • (7.10) List at least two real-world applications for hash tables.

Undirected Graphs

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

Directed Graphs

  • (8B.1) Describe the directed graph API.
  • (8B.2) Correctly use and explain terminology related to directed graphs.
  • (8B.3) Explain the difference between directed graphs and undirected graphs.
  • (8B.4) List two examples of real-world applications of weighted and non-weighted directed graphs.
  • (8B.5) Explain and illustrate a directed graph and a directed cycle.
  • (8B.6) Implement a directed graph with a vertex-indexed array of lists.
  • (8B.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.
  • (8B.8) Explain, with an illustration, Depth-First Search (DFS) in a directed graph.
  • (8B.9) Discuss the differences among pre-order, post-order, reverse post-order vertex orderings.
  • (8B.10) Explain, with an illustration, Breadth-First Search (BFS) in a directed graph.
  • (8B.11) List at least two real-world applications of directed graphs.
  • (8B.12) Explain the differences between a directed graph and a directed cycle.
  • (8B.13) Discuss the concept of reachability in directed graphs.
  • (8B.14) Given a directed graph, find the shortest path between one vertex and another.
  • (8B.15) Describe and illustrate a topological sort of a directed graph.
  • Insertion Sort
  • Selection Sort
  • (9A.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.
  • (9A.2) Determine the best case and worst case Big-O analysis of the selection sort.
  • (9A.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.
  • (9A.4) Determine the best case and worst case Big-O analysis of the insertion sort.
  •  

Mergesort

  • (9B.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.
  • (9B.2) Determine the best case and worst case Big-O analysis of the Mergesort.

Quicksort

  • (9C.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.
  • (9C.2) Determine the best case and worst case Big-O analysis of the Quicksort.
  • (9C.3) Explain the meanings of  “in place sort” and “stable sort”.
  • (9C.4) Indicate whether or not each sort (insertion, selection, merge, quick) is an “in place” sort.
  • (9C.5) Indicate whether or not each sort (insertion, selection, merge, quick) is a stable sort.
  • (9C.6) Explain the advantage of combining Insertion sort  with Quicksort (or Mergesort)  when sorting a large array.
  • (9C.7) Describe at least two ways  to “shuffle” items in an array.

Tries

  •