Skip to content

Latest commit

 

History

History
104 lines (70 loc) · 4.68 KB

general.md

File metadata and controls

104 lines (70 loc) · 4.68 KB

Data structures

Abstract data type

  • ADT is defined by behaviour (operations) and not concrete implementation. In other words, it is an implementation-independent representation of how data is organised.
  • Common ADTs: stack, queue, priority queue, dictionary

Abstract data type structure

  • ADTS is the actual structure of data used to store data
  • Common data structures that are used to implement data types: array, linked list, hash table, tree(s)

Array

  • An allocated block of memory that stores data of the same data type. For example, an array of 4 integers.

Tuple

  • An ordered group of elements (or items) that make a single (compound) structure
  • Tuples can container multiple types and are used to group elements together
  • This data structure is immutable hence cannot be modified and order is guaranteed
  • Elements are accessed by index
  • In functional programming tuples are implement as product types
thisistuple = ("one", "two", "three")

List

  • List is similar to an array but allows elements of various types. A list can store heterogeneous data.
  • It is growable, meaning it can dynamically expand if necessary
  • Lists support such operations as get(), insert(), remove(), removeAt(), etc.

Linked list

  • Linked list allows to store data anywhere in the memory
  • Each node in a linked list stores some data and the address to the next node
    • Singly -
    • Doubly -
    • Circularly -

Trie (prefix tree, digital tree)

  • Trie (derives from word retrieval) data structure is a very useful data structure when working with strings. Every tree leaf represents one string. Each node is exactly one character of the string.
  • Trie data structure is useful when looking for a string is a set of strings. This data structure is simple to build and search but can be expensive on memory.
-age // suffix; meaning - a result
storage // word

Trie

Resources

Suffix tree

  • Suffix tree is a form of a trie data structure that prepares strings for fast pattern matching operations. It contains i suffixes of i-character string.
  • Build a suffix tree - https://www.youtube.com/watch?v=qh2leThTv0Y

Dynamic programming

DP is an algorithm design style for solving complex programming problems.

  • Top down approach - recursion + memoization, start from end of the problem
  • Bottom up approach - dynamic programming table design, start from the beginning of the problem
  • Recursion is when a function calls itself
  • Memoization - remembering / caching function calculations and returning when same function get called again.
  • Directed acyclic graph (DAG) - is a directed graph, that contains nodes connecting edges without cycles. Directed graph edges go only one way (defined direction). It is impossible to traverse the entire graph starting at one edge. Acyclic means that that are no loops (cycles) in the graph, meaning that there is no way to go back from on node (vertex) to another via the edge. An example of where DAG is used is a topological sort algorithm. This algorithm can be used anywhere where we have dependencies (if one thing depends on another e.g. determining order of tasks in a Makefile).

Recursion

  • When a function keeps on calling itself until it reaches a final point
  • A base case is when a result gets computed immediately given the inputs to the function. It is the simplest, smallest instance of a problem that cannot be decomposed any further. Bases cases usually lay at the bottom which guarantees te recursion to be finite.
  • A recursive step is where the function gets called recursively
  • Recursion can have multiple base cases

Backtracking

  • Enables to go through all possible search options meaning that ways of arranging objects or ways of building them.

Resources

General resources