Please enable JavaScript.

Coggle requires JavaScript to display documents.

Computer Science (Strategy (Heuristics (save time with heuristics for a…

- - - - NP-complete problems
    - - What are the power and limits of computation?
      - What is a computer?
      - Not just a PC anymore: The Internet, server farms, supercomputers, multi-cores, …, nano, bio, quantum, etc
      - What is the power of computing, by machine and human
        together?
    - - invariant representations: Peter Naur, by Jeff Hawkins, creator of PalmPilot and Treo
      - “Computing Versus Human Thinking,” Peter Naur, Turing Award 2005 Lecture, CACM, January 200
    - - From nature:
        
        It’s not just 0’s and 1’s. Qubits
        
        “Biology is an information science.”. Geology too.
        
        Molecules/chemicals are processors of information (computer),
        carriers ofinformation (storage), and channels of information (communication)
      - To knowledge
        
        We are drowning in data. Data is dirt; knowledge is gold.
- - - - To avoid duplicated information, relational model splits related information into different tables. Primary key and foreign key
      - Normalized database - database that is organized in a way that is free of duplicate info
      - Schema migration scripts and tools upgrade the schema and transforms the data accordingly to change the database structure
      - combination of fields and restrictions
    - - almost every DBMS works with it
      - Joins are expensive to compute. They may consider every combination of rows from combined tables. Join is the greatest power and the main weakness of Relational Databases
      - Transactions - a list of database operations that must be executed atomically
    - - Uniqueness constraint - Indexes are often automatically created for fields that have un.constraint. It is neccesary to quickly check for uniqueness.
      - Sorting - Indexes help to fetch rows in the indexed fields' sorted order. Many DBMSs might refuse sorting non-indexed fields
      - Performance
        
        Indexes are awesome - they allow super fast quering and instant sorted data access
        
        The problem: when a new register is inserted or deleted from a table, all its indexes must be updated to reflect this. Morover, indexes occupy disc space
        
        To adjust the database for higher performance it's essential to know which indexes to keep and which to discard. Poor indexing is a major cause for slowdown in commercial systems
      - Mapping row IDs to their respective addresses in memory.
      - An index is essentially a self-balancing BST. Node keys are the values in the field we index. O(logn) for searching
  - - - Most widely known NoSQL type. Data entries are kept exactly the way they are needed for the application
      - Non-relational model expects us to duplicate info at each relevant place
      - It's hard to keep duplicated data updated and consistent
      - In return more flexibility: don't need to join rows, don't need fixed schemas, each data entry can have its own configuration of fields
      - A data entry is called a document. Related documents are grouped in a collection
      - NoSQL also create indexes for primary fields
    - - the simplest form of organized, persistent data storage
      - it's mainly used for caching
      - If you repeat a slow operation that always produces the same result, consider caching.
      - Also can use other database types for caching. Key-Value stores are superior when the cache is frequently accessed
    - - Data entries are stored as nodes, and relationships as edges
      - The most flexible type of database. Letting go tables and collections you can store data in an intuitive ways
      - Consider it when your data looks like a network. They are especially useful when there are many important relationships between pieces of data
    - - Volume, Velocity, Variety
      - Is often accosiated with NoSQL databases because of their added flexibility. It wouldnt be feasible to implement many types of Big Data applications with relational DBs
    - - Relational are data-centered: they maximize data structuring and eliminate duplication, regardless of how data will be needed
      - Non-relational are application-centered: they facilitate access and use according to your need
      - NoSQL allow to store massive, volatile, unstructured data fast and efficiently
  - - - Databases of several hundreds terabytes
      - DB systems that process several thousand simultaneous queries per second
      - Mission-critical DBs - need replicas
    - - Single-Master Replication
        
        One master, several slaves
        
        Each slave has a full replica. Master keeps them updated and delegates read queries to slaves.
      - Multi-Master Replication
        
        If a system must support a massive amount of simultaneous write queries - one master cannot handle that
        
        All computers in the cluster become masters. A load balancer is used to distribute queries equally.
        
        Each computer is connected to all others in the cluster
      - Sharding
        
        If a system recieves many write queries for large amounts of data, it's hard to syncronize database everywhere in the cluster. Some computers might not have enough storage
        
        One solution - partition the database among the computers
        
        To mitigate the risk of loosing parts of the data: sharding with replication. Each shard is served as a master-slave cluster
- - - - Very simple. Time complexity: O(n^2), space complexity: O(1)
      - Belongs to a big group of quadratic cost algorithms. We typically use them to sort small datasets <1000 items
    - - O(nlogn): pivot....several steps
    - - O(nlogn): split, sort, merge recursively
    - - A notable quadratic cost algorithm
      - Is very efficient at sorting nearly sorted datasets, even huge: O(n)
  - - - The simplest search algorithm: looke for all items one after another: O(n)
    - - More efficient, for structured data. If data is structured in a balanced BST: O(logn)
      - This process discards half the search space in each step
  - - - DFS
        
        Keep following edges going deeper and deeper into the graph
        
        When we reach a node that has no edges, go back to the previous node and continue
        
        We use Stack to keep track of exploration trail. The Backtracking strategy explores solutions this way.
        
        Is simpler to implement and consumes less memory: just need to store the parent node leading to the current node.
      - BFS
        
        Explores graph level by level
        
        Use Queue to keep track of nodes - the only difference from DFS
        
        Need to store the entire frontier of search process. Not practical for large graph
        
        Makes sense when you suspect the node you're looking for is not many layers from the start
      - Visit every node in the graph until you find the one you want
    - - Graph coloring problems arise when you have a fixed amount of "colors" (labels) and you must assign each node in the Graph a color. Nodes that are connected with an edge cannot have the same color.
      - Finding the minimum number of colors of a valid color assignment is a NP-problem - there are only exponential algorithms for it.
    - - DFS and BFS strategies are usable but bad for that.
      - Djkistra Algorithm
        
        One famous and very efficient way. It uses a Priority Queue to keep track of nodes to explore.
        
        A node's priority is the weight of the edges that take it to the starting node. This way, the next node to explore is always closest to where we started.
        
        There are cases where this algorithm cycles forever - a negative cycle - when edges can have negative weights
      - Bidirectional search
        
        Can be used to increase speed of search.
        
        Two search processes run simultaneously: one from the start, one from the destination point. When any node in one search area is also present in the other => we've got the path
        
        The search area involved in Bidirectional search is twice smaller than the Unidirectional search
      - Finding the shortest path between nodes is the most famous graph problem
    - - Algorithm runs in rounds. Each web page in the graph starts with equal number of points.
      - After each round, each page distributes it's points to the pages it has links to.
      - The process is repeated until every score is stabilized
      - Determining importance of nodes (web pages)
  - - - ex: airline companies, WWII
      - Many problems relating to networks and flows can be formulated in terms of linear equations and solved with Simplex
    - - Problems where the objective and constraints can be modeled using linear equations.
      - No coding is required to solve such problems. Solution: Simplex Method
      - Simplex solver works through smart exploration of the space of acceptable solutions: the optimum solution must be a corner point of the closed area - a point where lines representing constraints cross
      - Simplex check these corner points and picks the one that optimizes objective.
- - - - Model - a set of concept that represent a problem and it's characteristics
      - Mathematically described models can be adapted for computers using well established math techniques
- - - - are distinguished according to the operations that can be performed on the data: String, Boolean, Number
    - - is the specification of a group of operations that make sense for a given data type...describe how variables of a given data type are operated...that way we never manipulate a computer memory directly, but rely on these procedures.
    - - Simplicity
        
        make code simpler to understand and modify => focus on big picture of problem solving process of the algorithm
      - Flexibility
      - Reusability
      - Organization
        
        separation of concepts - parts of code that deal with same logical aspect should be grouped in their own, separate module
      - Convenience
      - Bug-fixing
  - - - integers & floating points, generic operations with them: addition, substraction, etc.
      - text
      - booleans
    - - Basic operations: push(e), pop()
      - LIFO
      - ex: undo feature in the text editor, backtracking without recursion
    - - Basic operation: enqueue(e), dequeue()
      - FIFO
      - ex: pizza delivery
    - - enqueue(e,p), dequeue()
      - assigning a priority level
      - ex: CPU processesing
    - - More flexible than Stack & Queue: reordering items, accessing items at any position
      - operations: insert(n,e), remove(n), get(n), sort(), slice(start,end), reverse()
      - A simpler ADT must be prefered when this flexibility isn't needed
    - - useful when we need to maintain an always sorted list
      - has fewer operations than the List: insert(e), remove(n), get(n)
    - - Used to store mappings between objects
      - operations: set(key, value), delete(key), get(key)
    - - represents unordered group of unique items
      - add(e), delete(e), list
  - - - Array
        
        a simplest way of allocating a bunch of items in computer's memory
        
        allocates a sequential space in the computer memory and writes items sequentially in that space
        
        Pros: this lets us access any item in array instantly
        
        is especially useful to implement Stack, but can also be used to implement Lists and Queues
        
        Cons: it can be impractical to allocate large amounts of sequential space in memory. Also removing or adding an item in the middle of array is problematic
      - Linked List
        
        items are stored in a chain of cells that don't need to be at sequential memory addresses. Memory for each cell is allocated as needed. Each cell has a pointer indicating the next cell
        
        Pros: no problem with growing. Easy to insert and delete in the middle
        
        Cons: always have to start from the first cell, can't instantly retrieve address of n-th item, don't know the address of the previous cell
      - Double Linked List
        
        with an extra: cells have two pointers - to the cell before and after
      - Arrays vs Linked Lists
        
        When the performance isn't an issue, we can rely on generic built-in ADT implementations and don't worry about data structures
        
        but when performance must be optimal or when working with a lower level language that doesn't have such features, you must decide which data structures to use
        
        Linked lists are preferable when
        
        you need insertions/deletions in the list to be extremely fast
        
        you don't need random, unordered access to data
        
        you insert or delete items in the middle of the list
        
        you cant evaluate the exact size of the list
        
        Arrays are preferable when
        
        you frequently need random unordered access to data
        
        you need extreme performance to access the items
        
        the number of items doesnt change throughout the execution, so you can easily allocate contiguous space of computer memory
      - Tree
        
        Like the Linked List, Tree employs memory cells that dont need to be contiguous in physical memory to store objects
        
        Cells also have pointers to other cells
        
        Unlike Linked Lists, cells and their pointers are not arranged as a linear chain of cells, but as a tree-like structure
        
        Trees are especially suitable for hierarchical data: file directory structure, command chain of an army
        
        Apart from the root node, every node in the tree must have exactly one parent node
        
        Nodes that don't have any children are leaf nodes
        
        A node's level is a size of it's path to the root node
      - Binary Search Tree
        
        Binary Heap
        
        Special type of BST in which we can find max or min item instantly. Is especially useful for implementing Priority Queues
        
        It costs O(1) to find max/min, because it's always the Root Node
        
        Searching or inserting nodes still costs O(logn)
        
        Additional restriction: a parent node must be greater or smaller than it's child nodes
        
        A special type of Tree that can be efficiently searched
        
        Nodes in BST can have at most two children
        
        And nodes are positioned according to their value/key: children nodes to the left must be smaller than the parent, and to the right - greater
        
        If the tree respects this property it is easy to search for a node with a given key/value pair within the tree
        
        Tree balancing
        
        We can end up with a tree of a very high height where many nodes have only one child. But we can rearrange node in a way so that the height is reduced
        
        A perfectly balanced tree has the minimum possible height
        
        Searching in a balanced BST with n items is O(logn). That's why this data structure is often chosen to implement Sets (which require finding if item is already present) and Maps (requires finding key-values)
        
        self-balancing binary trees
        
        However balancing is an expensive operation. To efficiently handle BST that change a lot self-balancing BST where invented: after inserting or deleting an item the tree always stays balanced
        
        Red-Black tree - famous example, colors nodes either black or red for its balancing strategy. Frequently used to implement Maps
        
        AVL Tree - another example. Require more time to insert and delete items than Red-Black trees, but are faster for retrieving items. Are often used to optimize performance in read-intensive scenarios
        
        B-Tree
        
        Generalization of Binary Tree. Nodes may store more than one item and have more than two children, making it efficient to operate with data in big chunks. Are commonly used in database systems
      - Graph
        
        Is similar to the Tree. But there is no parent nodes. Data is freely arranged as nodes and edges, any node can have multiple incoming and outgoing nodes.
      - Hash Table
        
        Allows finding items at O(1) time
        
        Similarly to Array, requires preallocating a big amount of memory. But unlike the Array, items are not stored in an ordered sequence
        
        The position an item occupies is "magically" given by a hash function: function outputs a random-looking number for a data. That number is interpreted as a memory position the data will be stored at.
        
        A problem: hash collision - both items will be stored at the same address. It's an overhead for CPU and memory, so we try to avoid it
        
        We ensure at least 50% of the space available to the Hash Table is free. Otherwise collisions would be too frequent causing a significant drop in performance
        
        Are often used to implement Sets and Maps. Allow faster insertions and deletions than tree-based structures. However they require a very large chunk of sequential memory to work properly
- - - - = RAM (Random Access Memory): is where we write instructions. It also stores the data to operate on.
      - Is devided into many cells. Each cell stores a tiny amount of data. Read or Write a memory cell - communicate it's numerical address
      - Memory is electrical component => we transmit cell addresses through wires as binary numbers. Each wire transmit a binary digit: with a higher voltage for "1" and a lower for "0"
      - There are two things memory can do with a given cell's address: get its value or store a new value. The memory has a special unit for setting its operational mode
      - Each memory cell stores an 8-digit binary number = byte
      - A group of wires used to transmit the same data is a bus: address bus (unidirectional - only recieve the data) & data bus (bidirectional - send and recieve)
    - - = CPU (Central Processing Unit): gets instructions and data from memory and performs calculations accordingly
      - CPU and RAM are constantly exchanging data: the CPU keeps on fetching instructions and data from memory, and occasionally stores outputs and partial calculations in it
      - Internal memory cells: registers. It can perform internal math calculations with numbers stored in these registers. It can also move data between RAM in these registers
      - Operations
        
        Computer code is essentially a sequence of numbers representing CPU operations.
        
        These operations are stored as numbers in RAM. We store input/output data, partial calculations and computer code, all mixed together in RAM
        
        The collection of all operations a CPU can do: instruction set. Each operation in the set is assigned a number
      - PC
        
        CPU is amazing because it can be instructed to write a new value to PC, causing the execution to branch or jump somewhere else in the memory
        
        CPU works in never-ending cycle, always fetching and executing instructions from memory. At the core of this cycle is Program Counter - a special register that stores the memory address of the next instruction to be executed
      - CPU Clock
        
        the number of basic operations it executes per second. 2MHz ~ 2 millions
        
        A machine instruction takes 5-10 basic operations to complete. 2MHz ~ 100s-1000s of instructions per second
        
        Modern desktop computers ans smartphones: 2 GHz - 100s of millions machine instructions per second
        
        Multicore CPUs. A quad-core 2GHz CPU: billion machine instructions
      - CPU Architectures
        
        x86 is now pretty standart. Same code can be executed on different computers
        
        Cellphones have different CPU architectures that a more power-efficient
        
        A different CPU architecture means a diferent instruction set, thus a different way to encode instructions as numbers
        
        First architectures: 4-bit - could operate (sum, compare, move) binary numbers of up to 4 digits in a single machine instruction
        
        32-bit: address bus with 32 wires allows addressing 2^32 bytes of memory = 4GB
        
        64-bit: is dominant today: 2^64 bytes of memory = 17 billion GB
      - big-endian vs little-endian
        
        store the numbers in CPU and RAM right-to-left or left-to-right
        
        Most computers are little-endian
        
        Internet traffic standartized in big-endian, because most of the early network routers had big-endian CPUs
      - Emulators
        
        Software that allows to run some code that was designed for a different CPU
        
        An emulators mimics the target machine - it pretends to have the same CPU, RAM and other hardware
  - - - Simple machines can be powerful enough to compute anything. For a machine to have universal computer power, it must be able to follow a porgram containing instructionsto:
      - Read and write data from memory
      - Perform conditional branching: if a memory address has a given value, jump to another point in the program
      - It doesnt matter how complex a computation is. It can be always expressed in terms of simple read/write/branch instructions. With enough time and memory these instructions can compute anything
    - - to run, a program must communicate with computer's operating system. With its help a program can work effortlessly with different hardware
      - Programs make special system calls, requesting operating system to perform required input/output operations
    - - Compilers may try to apply hundreds of optimization rules before producing a binary output
      - Thats why you shouldnt make your code harder to read in favour of micro-optimizations. In the end, compiler will do any trivial optimizations anyway
      - Modern compilers will rewrite simple recursive functions automatically
      - If you have performance issues, use profiling tools to discover bottlnecks in your code, and try to compute these parts in simpler way
    - - Code is executed by interpreter.
      - Is much slower than compiled code, but can be run immediately
    - - Given a compiled computer program, its impossible to recover its source code prior to compilation (at least for now)
      - But its possible to decode the binary program, transforming the numbers encoding CPU instructions into a human-readable sequence of instructions. This process - dissasembly
      - When we look at these instructions and try to figure out what they are doing - reverse engineering
    - - Main concept: software that anyone can use and modify freely
      - It's harder for malicious third parties and goverment agencies to insert surveillance backdoors into open-source systems, because they are open to public scrutinity
  - - - If memory access is slow, CPU has to sit idle. waiting for RAM to do its work
      - Storage space of CPU registers is usually limited to less than a thousand bytes. This means CPU registers constantly have to transfer data to and from RAM
      - Data in CPU registers is accessed nearly instantly by CPU, within just one cycle. The RAM, however, is way slower
      - Recent tech developments increased CPU performance exponentially, but not the memory speed. Difference - gap.
    - - Temporal: if a memory address is accessed, its probable it will be accessed again soon
      - Spatial: if a memory adress is accessed, its probable addresses that are adjacent to it are going to be accessed soon
    - - Growing L1 cache without slowing it down is difficult. After 50KB further increasing is expensive.
      - The better solution is to build additional L2 cache. ~200 KB. With L2, only ~10% of memory requests have to be directly fetched from RAM
      - L1/L2/L3 caches are so important that they take most of the silicon space inside a CPU chip
      - Better CPUs will have larger caches. Its often better to get a CPU with slower clock but larger cache
    - - Copy contents of memory addresses with high probability of being accessed close to CPU registers
      - With about 10KB of cache memory and L1 smart utilization of temporal and spatial locality, over half of RAM access calls can be fulfilled by this cache alone
    - - As we go down the hierarchy, more memory space is available, but at lower access speed
      - CPU registers => L1/L2/L3 caches => RAM (primary memory) => hard disc (secondary memory) => external storage => tertiary storage
      - Hard discs are very slow. CPU cannot directly access secondary memory. Programs stored in the secondary memory have to be copied to the primary memory first
      - Each time you boot a computer, your operation system has to be copied from the disc to RAM before the CPU can run it
    - - Never exhaust the RAM. Ensure all the data computer is handling fits the RAM.
      - Otherwise computer will constantly transfer data between the disc and RAM. This operation is extremely slow.
    - - It has been hard to significantly improve technology used in fast memories
      - On the other hand, "slow" memories are getting faster and cheaper
      - Caching principle can has been applied in different levels, also hybrid discs; SSD+magnetic
- - - - A value represents information
      - first-class citizens - very important
      - operations with values: can be created at runtime, can be passed as arguments to functions, can be returned by functions
    - - An expression produces a value
      - A value can be created in two ways: by writing a literal, or by calling a function
      - operator - another basic element in every programming language. An operator can join simple expressions to form more complex ones
      - A complex expression must always evaluate to a single value
      - Parentheses allow control over operator precedence
    - - A statement uses a value to give an instruction to a computer
      - examples: print, if, while-loop, for-loop statements
    - - Some progr. languages use special statements - definitions
      - They change a state of a program by adding an entity that didn't exist, like a new value or function
      - To refer to an entity we defined, we need to associate a name to it: name binding
  - - - In most progr. languages variables must have an assigned type. This way, the program knows how it should interpret 1s and 0s it reads in the variable memory block. This helps to spot errors when operating with variables
      - There are two ways to perform type checking: statically and dynamically
      - Static
        
        Declare the type of every variable before using it
        
        Extra optimization is applyed during compilation, allowing to spot possible bugs before you execute the code
        
        Can get boring declaring every variable
      - Dynamic
        
        Any variable can store any type of value
        
        When code is executed, extra type checking is performed when operating with variables.
    - - To avoid collisions, name bindings are not valid over the entire source code. The variable's scope defines where it is valid
      - The current context/environment is a set of all name bindings that are available in a program at a given point
      - global variables
      - namespace - the collection of all variables that are available globally. It should be kept as small as possible
  - - - A programming paradigm is a point of view of the coding realm. It will direct your coding style and technique
      - A paradigm will orientate how you approach the problem, the techniques you use, and the structure of your solution. Ex: Newtonian and Relativistics schools are different paradigms in physics
      - A paradigm is a specific collection of concepts and practices that define a field of science
      - You can use one or multiple paradigms in your program
      - It's best to use paradigms that the progr. language you are using is based on
      - Most coders only learn how to properly work with Imperative programming. Knowing about all three is important - it will enable you to benefit from the features and opportunities each progr. language offers
    - - Machine code programming
        
        Using mnemonics such as CP or MOV to write instructions: Assembly language
        
        Is used in an electronic microwave or computer system in a car. Also is used in sections of code where extreme performance is needed, where saving even a few CPU cycles is relevant
        
        Lower level languages sometimes support insertion of machine language within the normal programming language's code
        
        Writing in machine code gives you maximum control of what CPU is doing when running your code
      - Structured programming
        
        In the beginning was GOTO and JUMP => spaghetti code
        
        Using control structures (if, else, while, for...) enabled programs to be much more easy written and debugged. From 1968.
      - Procedural programming
        
        Next advance in the art of programming. It allows code to be organized into procedures, to avoid code replication and to increase reusability.
        
        This improved structures programming even further. Using procedures makes it much easier to group related pieces of code, while separating them into different logical parts
      - Is about instructing computer on what it must do exactly at each step using specific commands
      - Each command changes computer's state
      - The sequence of commands that constitutes a program is followed, one after another
      - This was the first programming paradigm, as its a natural extension of the way computers work
      - In the end, every computer program is ultimately executed by computer under this paradigm (by CPU instructions, one after another)
    - - Functional programming
        
        In this paradigm, functions are more then just procedures. They are first-class citizens
        
        They are used to declare relationships between two or more items, much like math equations
        
        They are treated the same way as any other primitive data types.
        
        Functions can recieve other functions as arguments, and return functions as outputs => high-order functions, because of they high expressive power
        
        Many mainstream progr. languages are incorporating such elements from functional programming => take advantage of their marvelous expressivenes whenever possible
        
        Ex: generic filter, map, reduce functions
        
        Syntactic sugar - added syntax that lets you write expressions in simpler and shorter forms. Ex: list comprehensions in Python
        
        A function that has a closure - "remembers" stuff and can access the environment (some variables) of it's enclosed values.
        
        Using closure we can split execution of a function which takes different arguments into more steps. This is called currying
        
        Closure "attaches" some data to the code
        
        lazy evaluation - important characteristic of functional progr. languages
        
        Closures are also used to generate a set of related functions that follow a template. Using a function template can make your code more readable and avoid duplication
        
        Closures can also be used to manage a function's internal state
      - Pattern matching
        
        Func. programming allows you to treat functions like math functions. WIth math, we can write how functions behave according to the input
        
        Pattern matching - the process of recognizing a pattern
      - It's about declaring what you want, and not how you want it done. In many scenarios it allows programs to be much simpler and shorter.
      - Purely functional languages
        
        In these languages all values assigned to variables are non-mutant. We call that single assignment
        
        Some progr. languages are strictly functional: all the code is equivalent to purely mathemetical functions. The order of statements in the code don't interfere the code's behaviour
        
        Since there is no program state, there is no point-in-time for the variable to change
        
        Computing in a strict functional program is merely a matter of evaluating functions and matching patterns
    - - Whenever your program is a solution to a set of logical formulas
      - The greatest advantage of this paradigm is that programming itself is kept to a minimum. Only facts, statements and queries are presented to a computer
      - The computer is in charge of finding the best way to search the solution space and present the results
      - The coder express logical assertions about the situation. Then queries are made to find out answers from the model that was provided. The computer is in charge of interpreting the logical variables and queries
      - This paradigm isnt very well used in the mainstream, but in case of AI, NLP, remember to look into this
      - Is preferred paradigm when working in some very specific contexts