Home

Wait-Free Synchronization Lock Free Synchronization mechanisms that do not use locks. Wait Free If lock-free synchronization also guarantees that each operation finishes in a bounded number of steps Simplicity The implementation of a concurrent object may use other simpler concurrent objects Whether it allows multiple readers or writer...

Constraint Satisfication Problems Variables $\vec{X}=X_1,…,X_n;$ each variable $X_i$ has a domain $D_i$ Constraints $\vec{C}$ Constraint scope: which variables are involved constraint relation: what is the relation between them Objective Find a legal assignment ($y_1,…,y_n$) of values to variables $y_i\in D_i$ for all $i \in [n]$...

435. Non-overlapping Intervals Solutions Sort the intervals by right limit. Loop from left, remove next if it overlaps with current interval. This is to ensure that the removed interval is “largest” interval.

226. Invert Binary Tree Solutions Recursive Solution Invert children of the root Assign left child to right, assign right child to left.

Best-First Search Idea Use an evaluation function $f(n)$ for each node $n$ Cost estimate -> Expand node with lowest evaluation/cost first Implementation Frontier = priority queue ordered by nondecreasing cost $f$ Greedy Best-First Search Evaluation function $f(n)=h(n)$ (heuristic function) = estimated cost of cheapest path from $n$ to...

Game Components initial state $s_0$ states players: $PLAYER(s)$ defines which player has the move in state $s$ actions: $ACTIONS(s)$ returns set of legal moves in state $s$ transition model: $RESULT(s, a)$ returns state that results from the move $a$ in state $s$ terminal test $TERMINAL(s)=true$ iff game end utility func...

98. Validate Binary Search Tree Solutions Solution 1: Keep lower bound and upper bound for each node Recursively check if a node is within the range Solution 2: Inorder Traversal

Fully observable, deterministic, discrete environment. Problem Formulation Goal Test Path Cost Tree Search Start at the source node, keep searching until we reach a goal state. Frontier: Nodes that we have seen but haven’t explored yet At each iteration, choose a node from the frontier, explore it, and add its neighbo...