CSE 373: Topics Covered (post-midterm: July 24 August 16, 2017) – (Note that this is only a big-picture overview it leaves out a lot of detail) – Graphs Sorting Algorithms General knowledge & terminology Terminology Mathematical representation Stable sort ( G = (V, E), etc.) In-place sort Undirected & Directed Graphs External sort Self Edges Comparison Sort Weights Insertion Sort Paths Selection Sort Cycles Heapsort (including in-place version) Connectedness Merge Sort (including time- & Trees as graphs versions) DAGs Quicksort (including different pivot Density & Sparsity rules and in-place quicksort) Graph data structures Using cutoffs Adjacency Matrix Other Sorts Adjacency List Conditions that let you use them When to use which and why Bucket Sort (a.k.a. Bin Sort) Radix Sort Graph algorithms How to sort massive data Topological Sort What algorithms make the most What it is sense and why Necessary conditions How to sort Two algorithms for topological sort For each algorithm: Traversals Worst- best-case scenarios & run Depth First Search (DFS) times Breadth First Search (BFS) Other pro's/con's of each When to use which When to use Shortest path For unweighted graphs General Algorithms Knowledge For weighted graphs (Dijkstra's Analyzing algorithms algorithm) Correctness (less emphasis here) Two approaches to Dijkstra's, when Efficiency to use which Several algorithm types Spanning Trees Greedy algorithms Approach #1: DFS Dynamic programming Approach #2: Add acyclic Divide-and-conquer Minimum Spanning Tree (MST) P vs NP Prim's Algorithm Kruskal's Algorithm
CSE 373: Topics Covered (post-midterm: July 24 – August 16, 2017) (Note that this is only a big-picture overview – it leaves out a lot of detail) Graphs General knowledge & terminology Mathematical representation ( G = (V, E), etc.) Undirected & Directed Graphs Self Edges Weights Paths Cycles Connectedness Trees as graphs DAGs Density & Sparsity Graph data structures Adjacency Matrix Adjacency List When to use which and why Graph algorithms Topological Sort What it is Necessary conditions Two algorithms for topological sort Traversals Depth First Search (DFS) Breadth First Search (BFS) When to use which Shortest path For unweighted graphs For weighted graphs (Dijkstra's algorithm) Two approaches to Dijkstra's, when to use which Spanning Trees Approach #1: DFS Approach #2: Add acyclic Minimum Spanning Tree (MST) Prim's Algorithm Kruskal's Algorithm Sorting Algorithms Terminology Stable sort In-place sort External sort Comparison Sort Insertion Sort Selection Sort Heapsort (including in-place version) Merge Sort (including time- & versions) Quicksort (including different pivot rules and in-place quicksort) Using cutoffs Other Sorts Conditions that let you use them Bucket Sort (a.k.a. Bin Sort) Radix Sort How to sort massive data What algorithms make the most sense and why How to sort For each algorithm: Worst- best-case scenarios & run times Other pro's/con's of each When to use General Algorithms Knowledge Analyzing algorithms Correctness (less emphasis here) Efficiency Several algorithm types Greedy algorithms Dynamic programming Divide-and-conquer P vs NP
Section%209%20-%20Materials%20Covered.docx