data structure

COMP2521 Data Structures & Algorithms Week 5.2 Graph Implementations   1 In this lecture Why? Different graph implementations have different pros and cons, and we should try and understand the difference What? Array of edges graph Adjacency Matrix graph Adjacency List graph   2 Properties of Graphs Terminology: |V| and |E| (cardinality) normally written just

COMP2521 Data Structures & Algorithms Week 1.1 Introduction Relevance to your program Assumed Knowledge Assume that you are at least a mediocre C programmer Produce a program from a specification Use fundamental data structures (char, int, float, arrays, structs, pointers, linkedlists) Need to revise?   Structs Pointers Malloc Linked Lists https://www.cse.unsw.edu.au/~cs2521/18s2/videos/structs.html https://www.cse.unsw.edu.au/~cs2521/18s2/videos/pointers.html https://www.cse.unsw.edu.au/~cs2521/18s2/videos/malloc.html https://www.cse.unsw.edu.au/~cs2521/18s2/videos/linked_list.html Why

COMP2521 Data Structures & Algorithms Week 9.3 Tries   1 In this lecture Why? Storing a large set of strings naively can be costly, we need a more efficient way What? Tries Tries insert Tries lookup 2 Tries Tries are a data structure for representing strings that support O(L) lookup and insertion (where L is

COMP2521 Data Structures & Algorithms Week 8.5 Sort Summary   1 Sorting Summray Comparisons Extra storage required? Stability Adaptive Selection N^2 No Possible No Insertion N^2 No Possible Possible if it stops can when position is found Bubble N N^2 No Possible Possible if it terminates when no swaps Merge N*log(N) Yes Possible Possible Quick

COMP2521 Data Structures & Algorithms Week 4.3 2-3-4 Trees (B-Tree of order 4) 1 In this lecture Why? Storing one item per node results in a lot of traversals happening, which can lead to slower lookups in trees What? 2-3-4 Trees Data Structure Insertion Pseudocode   2 Search Cost When analysing search costs in BSTs:

COMP2521 Data Structures & Algorithms Week 5.3 Graph Traversal   1 In this lecture Why? Graphs aren’t very useful if all we’re doing is storing things in them. We need to effectively search and traverse them to gather information What? Traverse and searching a graph Breadth-first-search Depth-first-search   2 Why do we use graphs? Allow

COMP2521 Data Structures & Algorithms Week 5.4 Graph Algorithms   1 In this lecture Why? There are a range of further algorithms that can be used to explore graphs What? Cycle Checking Connected Components Hamiltonian Path and Circuit Euler Path and Circuit   2 Cycle Checking A graph has a cycle if, at any point