## 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.

- Logistics slides
- Lecture slides A
- Textbook readings 1.1, 1.4, 1.5
- Book videos
- Lecture slides B (Union-Find)
- Book videos (Union-Find)
- Tools
- Using the Book Standard Libraries

- 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.

- Lecture slides
- Textbook reading 1.3
- Book videos

- 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.

- Lecture slides
- Textbook reading 3.2
- Book videos

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.

- Lecture slides
- Textbook reading 3.3
- Book videos

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.

- Lecture slides
- Textbook reading 2.4
- Book videos

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.

- Lecture slides
- Textbook reading 3.4
- Book videos

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.

- Lecture slides
- Textbook reading 4.2
- Book videos

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.

- Lecture slides
- Textbook reading 4.1
- Book videos

- Insertion Sort
- Selection Sort

- (9A.1) Given an array of values, give a step-by-step illustration of executing the
on the array. State the array contents after each pass of the sort.*selection 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
on the array. State the array contents after each pass of the sort.*insertion sort* - (9A.4) Determine the best case and worst case Big-O analysis of the insertion sort.

- Lecture slides
- Textbook reading 2.1
- Book videos

Mergesort

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

- Lecture slides
- Textbook reading 2.2
- Book videos

Quicksort

- (9C.1) Given an array of values, give a step-by-step illustration of executing the
on the array. State the array contents after each partition.*Quicksort sort* - (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.

- Lecture slides
- Textbook reading 2.3
- Book videos