Depth-first search

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking. Extra memory, usually a stack, is needed to keep track of the nodes discovered so far along a specified branch which helps in backtracking of the graph. A version of depth-first search was investigated in the 19th century by French mathematician Charles Pierre Trémaux as a strategy for solving mazes. Properties The time and space analysis of DFS differs according to its application area. In theoretical computer science, DFS is typically used to traverse an entire graph, and takes time O(|V| + |E|), where |V| is the number of vertices and |E| the number of edges. This is linear in the size of the graph. In these applications it also

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (38)

Related publications

Related people (3)

Related people

Related units (1)

Related units

Related concepts (24)

Related concepts

Related courses (6)

Related courses

Related lectures (7)

Related lectures

Horizontal side-channel full key recovery on ephemeral SIKE

Aymeric Genet, Novak Kaluderovic, Natacha Yolande Emmanuel Marie Linard de Guertechin

This paper describes the first practical single-trace side-channel power analysis of SIKE. The attack exploits the nature of elliptic curve point addition formulas which require the same function to be executed multiple times. We target the three point ladder which involves a loop of a double-and-add procedure, of which each iteration depends on a single bit of the private key. We show how a single trace of a loop iteration can be segmented into different power traces on which several 32-bit words can be hypothesised based on the current value of the private key bit. This segmentation enables a classical correlation power analysis in an extend-and-prune approach. Further error-correction techniques based on depth-search are suggested. The attack was experimentally verified on an STM32F3 featuring a Cortex-M4 microcontroller which runs the SIKEp434 implementation adapted to 32-bit ARM. We obtained a resounding 100% success rate recovering the full private key in each experiment. Finally, we provide a simple countermeasure with a negligible overhead which mitigates our attack successfully.

2021

Finding Second-Order Stationary Points in Constrained Minimization: A Feasible Direction Approach

Shaul Nadav Hallak

This paper introduces a method for computing points satisfying the second-order necessary optimality conditions for nonconvex minimization problems subject to a closed and convex constraint set. The method comprises two independent steps corresponding to the first- and second-order conditions. The first-order step is a generic closed map algorithm, which can be chosen from a variety of first-order algorithms, making it adjustable to the given problem. The second-order step can be viewed as a second-order feasible direction step for nonconvex minimization subject to a convex set. We prove that any limit point of the resulting scheme satisfies the second-order necessary optimality condition, and establish the scheme's convergence rate and complexity, under standard and mild assumptions. Numerical tests illustrate the proposed scheme.

SPRINGER/PLENUM PUBLISHERS2020

LF-Net: Learning Local Features from Images

Pascal Fua, Yuki Ono, Eduard Trulls Fortuny, Kwang Moo Yi

We present a novel deep architecture and a training strategy to learn a local feature pipeline from scratch, using collections of images without the need for human supervision. To do so we exploit depth and relative camera pose cues to create a virtual target that the network should achieve on one image, provided the outputs of the network for the other image. While this process is inherently non-differentiable, we show that we can optimize the network in a two-branch setup by confining it to one branch, while preserving differentiability in the other. We train our method on both indoor and outdoor datasets, with depth data from 3D sensors for the former, and depth estimates from an off-the-shelf Structure-from-Motion solution for the latter. Our models outperform the state of the art on sparse feature matching on both datasets, while running at 60+ fps for QVGA images.

NEURAL INFORMATION PROCESSING SYSTEMS (NIPS)

CS-250: Algorithms

The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, major algorithmic paradigms such as dynamic programming, sorting and searching, and graph algorithms.

CS-430: Intelligent agents

Software agents are widely used to control physical, economic and financial processes. The course presents practical methods for implementing software agents and multi-agent systems, supported by programming exercises, and the theoretical underpinnings including computational game theory.

COM-308: Internet analytics

Internet analytics is the collection, modeling, and analysis of user data in large-scale online services, such as social networking, e-commerce, search, and advertisement. This class explores a number of the key functions of such online services that have become ubiquitous over the past decade.

Glossary of graph theory

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges. Symbols A

Graph theory

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices (also called no

Tree (data structure)

In computer science, a tree is a widely used abstract data type that represents a hierarchical tree structure with a set of connected nodes. Each node in the tree can be connected to many children (d