Heuristic paper “A Formal Basis for the Heuristic Determination of Minimum Cost Paths”, Peter E. Hart, Nils J. Nilsson, and Bertram Raphael. Definitions For any subgraph \(G_s\) and any goal set \(T\) and starting state \(s\): Let \(f^*(n)\) be the actual cost of an optimal path constrained through \(n\), from \(s\) to \(n\) to a preferred goal node \(n\). From this definition, the (‘unconstrained’) optimal path can be written as \(f^*(s) = h^*(s)\), where \(h^*(n)\) is the optimal path from node \(n\) to the preferred goal node of \(s\).

What is it a distributed runtime uses pipelines for execution exactly-once state consistency lightweight checkpoint iterative processing windows semantics out-of-order processing 2 architecture cluster client job manager task manager (1 or more) client takes a program xforms to dataflow graph submits to job manager creates data schema and serializers cost-based query optmization job manager coordinates distributed execution of dataflow tracks state and progress of each operator and stream schedules new operators coordinates checkpoints and recovery persists minimal set of data for checkpoint and recovery task manager executes one or more operators report status to job manager maintain buffer pools to buffer or materialize streams maintain network connections to exchange of streams between operators 3.

Creating a bot on discord While there are some samples in discord.py. The API is fairly flat and hard to navigate. Here are the links to getting started: commands Understanding the context The Context (ctx) is often the first argument in the functions from @bot.command. This ctx contains most of the things needed to identify the message triggering the robot to respond (ctx fields): guild - on which server the robot was triggered message - the message of the command author - the author of the message send() - a function that allows the robot to respond back as a response to the trigger From this it is obvious you need some other way of getting at the channel where the message was sent.

Definition of a tree (Taken from Wikipedia) A tree is an undirected graph \(G\) that satisfies any of the following equivalent conditions: \(G\) is connected and acyclic (contains no cycles). \(G\) is acyclic, and a simple cycle is formed if any edge is added to \(G\). \(G\) is connected, but would become disconnected if any single edge is removed from \(G\). \(G\) is connected and the 3-vertex complete graph \(K_3\) is not a minor of \(G\).

It is easy see that if you start in a spot in the diagonal, you can get back to the diagonal in two moves. Say E-NE followed by N-NE, where I am using the the North, South, East and West conventions. Similarly for a knight at the x-axis you can get back to the x-axis with E-NE followed by E-SE. Let’s take a look at the diagonal section of 4,4,4 (pink), since I can get back to the diagonal in two moves, the next section has 6,6,6 (beige).

Aggregation difficulties content tailored to each user filter item with privacy checks for each user impossible to aggregate and filter when content is crated resolve data dependencies and privacy check each time content is viewed pull vs push social graph? extreme read demands on graph data store Memcache rapid deployment data mapping cache invalidation client code that is deployed frequently created abstractions for graphcs r/w objects (nodes) associations (edges) direct access to MySQL deprecated for graph data tyles Tao service implements objects and association model motivation encapsulating failures in the PHP API access graph easily from non-PHP serivces problems with lookaside cache architecture Inefficient edge lists KV cache is not good semantic fit for lists of edges queries must fetch the entire edge list list support would help make changes to single edge causes entire list to be reloaded requires coordination of incremental updates to cached lists Distributed control logic L-A $ control logic is run on clients clients don’t communicate with each other increases the number of failure modes difficult to avoid thundering herds Nishtala et al.

Requirements real-time aggregate dispersed data access hot set scale refs [1,2,5,6,12,14,34,36] Front-end cluster read heavy workload (100:1 R/W) wide fanout handle failures 10 Mops/s Q: what is a wide fanout Multiple FE clusters single geo region control data replication data consistency 100 Mops/s Multiple regions muliple geo regions storage replication data consistency 1 Bops/s Pre-memcached High fanout data dependency graph for a small user request Look-aside cache why deletes over set

polynomials \[ f(x) = A_0 + A_1 x + A_2 x^2 + \cdots + A_{n-1} x^{n-1} \] roots \begin{eqnarray} x^{n} &=& 1 \\\ x &=& e^{i \frac{2\pi}{n}} \end{eqnarray} Call \(e^{i \frac{2\pi}{n}} = w_n\) the fundamental, then there are \(n\) such roots, \(w_n^k\) for \(k = 0,\cdots,n-1\). The fourier transform is a vector of the polynomial evaluated at each of the \(k\) roots. \[ F(k) = f(w_n^k) \] The FFT is a divide and conquer algorithm where instead of doing \(O(n)\) computations for each fourier coefficient \(F(k)\), we break up the problem into 2 subproblems of size \(n/2\) and do a merge which is of order \(n\).

Segment tree Preliminaries The data structure in this segment tree information according to Antti Laaksonen in the Competitive Programmer’s Handbook comes from [62] P. Stańczyk. Algorytmika praktyczna w konkursach Informatycznych, MSc thesis, University of Warsaw, 2006. Basically the original range is stored at some offset that correspond to largest power of two that is greater or equal to the size of the range. For example a size 16 array would be stored at an offset of 16 in the array.

questions what is the interface provided simple k,v store what are the guarantees discussed strong and eventual consistency chain replication where are requests handled? write at head read at tail what is the dotted line going back from tail to head reply to the “write” client - committed why is this cheaper than other topologies because of pipelining of the writes down the chain what consistency does CR achieve?