Data Structures and Algorithms
This summary delves into the underlying data structures and main operations of arrays, linked lists, queues, stacks, trees, priority queues, maps, ordered maps, and graphs. It covers a wide range of topics including insertions, deletions, traversals, and various operations performed on different data structures.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Data Structures and Algorithms A SUMMARY
Data Structures Underlying Data Structures Main Operations Data Structures Arrays, Linked lists Queues, Stacks Trees Priority Queues Maps Ordered Maps Graphs
Data Structures Underlying Data Structures Main Operations Data Structures Arrays, Linked lists Queues, Stacks Trees Arrays, Linked lists Arrays, Linked structures Priority Queues Arrays, Linked lists, Heaps Maps Arrays, Hash tables Ordered Maps Sorted arrays, Skip lists, Binary search trees , AVL trees, (2,4) trees Adjacency lists, matrices (arrays), Edge lists Graphs
Data Structures Underlying Data Structures Main Operations Data Structures Arrays, Linked lists Get, Set, Traverse, Insert, Delete Queues, Stacks Trees Arrays, Linked lists Insert: enqueue, push Delete: dequeue, pop Children, Parent Traverse: preorder, inorder, postorder, breadth-first Insert: put Delete: removeMin Set: replaceKey, replaceValue Find: get Insert: put; Delete: remove Map operations plus floorEntry, ceilingEntry subMap getAdjacentVertices, getEdge Insert/delete vertex/edge Traverse: depth-first, breadth-first Arrays, Linked structures Priority Queues Arrays, Linked lists, Heaps Maps Arrays, Hash tables Ordered Maps Sorted arrays, Skip lists, Binary search trees , AVL trees, (2,4) trees Adjacency lists, matrices (arrays), Edge lists Graphs
Data Structures Underlying Data Structures Main Operations Data Structures Arrays, Linked lists Get, Set, Traverse, Insert, Delete Queues, Stacks Trees Arrays, Linked lists Insert: enqueue, push Delete: dequeue, pop Children, Parent Traverse: preorder, inorder, postorder, breadth-first Insert: put Delete: removeMin Set: replaceKey, replaceValue Find: get Insert: put; Delete: remove Map operations plus floorEntry, ceilingEntry subMap (Traverse) getAdjacentVertices, getEdge Insert/delete vertex/edge Traverse: depth-first, breadth-first Arrays, Linked structures Priority Queues Arrays, Linked lists, Heaps Maps Arrays, Hash tables Ordered Maps Sorted arrays, Skip lists, Binary search trees , AVL trees, (2,4) trees Adjacency lists, matrices (arrays), Edge lists Graphs
General Algorithm Types Types Characteristics Examples Brute Force try all possibilities usually the baseline algorithm Basic pattern matching
General Algorithm Types Types Characteristics Examples Brute Force try all possibilities usually the baseline algorithm Basic pattern matching Greedy given multiple possibilities at each iteration select the best one and do not look back may not be optimal for some problems Dijkstra (Shortest Path), Kruskal, Prim (Minimum Spanning Tree), Huffman (Compression)
General Algorithm Types Types Characteristics Examples Brute Force try all possibilities usually the baseline algorithm Basic pattern matching Greedy given multiple possibilities at each iteration select the best one and do not look back may not be optimal for some problems Dijkstra (Shortest Path), Kruskal, Prim (Minimum Spanning Tree), Huffman (Compression) Divide and Conquer decompose into separate subproblems and compose solutions usually recursive and top-down Mergesort, Quicksort
General Algorithm Types Types Characteristics Examples Brute Force try all possibilities usually the baseline algorithm Basic pattern matching Greedy given multiple possibilities at each iteration select the best one and do not look back may not be optimal for some problems Dijkstra (Shortest Path), Kruskal, Prim (Minimum Spanning Tree), Huffman (Compression) Divide and Conquer decompose into separate subproblems and compose solutions usually recursive and top-down Mergesort, Quicksort Dynamic programming decompose into reoccurring subproblems and compose solutions store sub-solutions and use bottom-up Longest Common Subsequence, Matrix Chain Multiplication
Leading to Term Project Lab exercises Understanding of Data Structures and Algorithms (DS&A) Homework assignments Implementation of DS&A further understanding and implementation issues Term project Choose/design/implement DS&A deeper understanding tradeoffs and which to use Standard libraries for data structures might not be enough
Problem Solving & Term Project Quality of solution Accuracy/points/ Algorithms Speed of solution Time Algorithms and data structures Space usage of solution Memory Data structures
Final Exam Dec 9, Monday, 6-8pm, regular classroom As stated in the syllabus (and FIT website) Graphs , Text Processing, Search Trees, Sorting Materials after Test 2 (indirectly on prior materials) Christmas Special Extra credit More questions/points
