Lecture

Basic Ingredients of Algorithms

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

In course

CS-119(d): Information, Computation, Communication

L'objectif de ce cours est d'introduire les étudiants à la pensée algorithmique, de les familiariser avec les fondamentaux de l'Informatique et de développer une première compétence en programmation (langage C++). ...

Description

This lecture introduces the basic elements of algorithms, including formalization, data handling, instructions, and control structures. It covers the formal definition of algorithms by mathematicians like Gödel and Turing, the use of variables, elementary instructions, and control structures. The lecture explains how algorithms work on data, the importance of variables, and the distinction between elementary and non-elementary instructions. It also discusses the necessity of control structures for complex algorithms, presenting examples of conditional branches and loops. Additionally, it explores the creation of algorithms for solving second-degree equations, illustrating the process with a concrete example. The lecture emphasizes the fundamental concepts required to understand and design algorithms effectively.

Instructor

Jean-Cédric Chappelier

Jean-Cédric Chappelier is currently senior researcher and lecturer in Computational Linguistics at the Ecole Polytechnique Fédérale de Lausanne (Switzerland). He holds an Ms.Sci. and a Ph.D. in Computer Science from the Ecole Nationale Supérieure des Télécommunications de Paris (France).

Official source

Related concepts (32)

Instructions per cycle

In computer architecture, instructions per cycle (IPC), commonly called instructions per clock is one aspect of a processor's performance: the average number of instructions executed for each clock cycle. It is the multiplicative inverse of cycles per instruction. While early generations of CPUs carried out all the steps to execute an instruction sequentially, modern CPUs can do many things in parallel.

Instruction set architecture

In computer science, an instruction set architecture (ISA), also called computer architecture, is an abstract model of a computer. A device that executes instructions described by that ISA, such as a central processing unit (CPU), is called an implementation. In general, an ISA defines the supported instructions, data types, registers, the hardware support for managing main memory, fundamental features (such as the memory consistency, addressing modes, virtual memory), and the input/output model of a family of implementations of the ISA.

Instructions per second

Instructions per second (IPS) is a measure of a computer's processor speed. For complex instruction set computers (CISCs), different instructions take different amounts of time, so the value measured depends on the instruction mix; even for comparing processors in the same family the IPS measurement can be problematic. Many reported IPS values have represented "peak" execution rates on artificial instruction sequences with few branches and no cache contention, whereas realistic workloads typically lead to significantly lower IPS values.

Complexity class

In computational complexity theory, a complexity class is a set of computational problems "of related resource-based complexity". The two most commonly analyzed resources are time and memory. In general, a complexity class is defined in terms of a type of computational problem, a model of computation, and a bounded resource like time or memory. In particular, most complexity classes consist of decision problems that are solvable with a Turing machine, and are differentiated by their time or space (memory) requirements.

Instruction pipelining

In computer engineering, instruction pipelining is a technique for implementing instruction-level parallelism within a single processor. Pipelining attempts to keep every part of the processor busy with some instruction by dividing incoming instructions into a series of sequential steps (the eponymous "pipeline") performed by different processor units with different parts of instructions processed in parallel. In a pipelined computer, instructions flow through the central processing unit (CPU) in stages.

Related lectures (64)

Solving Parity Games in Practice

Explores practical aspects of solving parity games, including winning strategies, algorithms, complexity, determinism, and heuristic approaches.

Complexity of Algorithms

Explores algorithm complexity, analyzing efficiency and worst-case scenarios of sorting algorithms.

Algorithmic Complexity: Definition and Examples

Explores algorithm correctness, worst-case complexity analysis, and efficiency comparison based on input size.

Linear Algebra: Efficiency and Complexity

Explores constraints, efficiency, and complexity in linear algebra, emphasizing convexity and worst-case complexity in algorithm analysis.

VLIW Architectures: Compilers and Instruction Level Parallelism