Lecture

Implementation of Sets (I)

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-108: Practice of object-oriented programming

Les étudiants perfectionnent leurs connaissances en Java et les mettent en pratique en réalisant un projet de taille conséquente. Ils apprennent à utiliser et à mettre en œuvre les principaux types de collections (listes, ensembles, tables associatives), e ...

Description

This lecture focuses on the implementation of sets, starting with a naive list-based approach and then moving on to a more efficient hash table-based implementation. The instructor explains the design of classes and interfaces, such as the S7 interface for simplified sets and the S abstract 7 class. The lecture covers methods like add, remove, contains, and iterator, emphasizing the differences between sets and lists. The S abstract 7 class is described as similar to S abstract list but tailored for sets. The lecture concludes by introducing the S list 7 class, a simplified version of the hash table-based implementation SH7, setting the stage for further exploration in subsequent videos.

Instructor

Michel Schinz

Teaching & PhD Courses Advanced compiler construction CS-420 Students learn several implementation techniques for modern functional and object-oriented programming languages. They put some of them into practice by developing key parts of a compiler and run time system for a simple functional programming language. Practice of object-oriented programming CS-108 Students improve their knowledge of Java and put it into practice by implementing a sizeable project. They learn how t

Official source

Related concepts (32)

Hash table

In computing, a hash table, also known as hash map, is a data structure that implements an associative array or dictionary. It is an abstract data type that maps keys to values. A hash table uses a hash function to compute an index, also called a hash code, into an array of buckets or slots, from which the desired value can be found. During lookup, the key is hashed and the resulting hash indicates where the corresponding value is stored.

Family of sets

In set theory and related branches of mathematics, a collection of subsets of a given set is called a family of subsets of , or a family of sets over More generally, a collection of any sets whatsoever is called a family of sets, set family, or a set system. A family of sets may be defined as a function from a set , known as the index set, to , in which case the sets of the family are indexed by members of .

Disjoint sets

In mathematics, two sets are said to be disjoint sets if they have no element in common. Equivalently, two disjoint sets are sets whose intersection is the empty set. For example, {1, 2, 3} and {4, 5, 6} are disjoint sets, while {1, 2, 3} and {3, 4, 5} are not disjoint. A collection of two or more sets is called disjoint if any two distinct sets of the collection are disjoint. This definition of disjoint sets can be extended to families of sets and to indexed families of sets.

Hash function

A hash function is any function that can be used to map data of arbitrary size to fixed-size values, though there are some hash functions that support variable length output. The values returned by a hash function are called hash values, hash codes, digests, or simply hashes. The values are usually used to index a fixed-size table called a hash table. Use of a hash function to index a hash table is called hashing or scatter storage addressing.

Set (mathematics)

A set is the mathematical model for a collection of different things; a set contains elements or members, which can be mathematical objects of any kind: numbers, symbols, points in space, lines, other geometrical shapes, variables, or even other sets. The set with no element is the empty set; a set with a single element is a singleton. A set may have a finite number of elements or be an infinite set. Two sets are equal if they have precisely the same elements. Sets are ubiquitous in modern mathematics.

Related lectures (32)

Sets and Relations

Introduces sets, Cartesian product, order importance, and relations on sets.

Sets and Functions

Introduces sets and functions, covering union, intersection, complement, functions terminology, and set operations analogies.

Sets, Functions and Relations: Organisational Questions

Covers organizational aspects, introduces Kahut for quizzes, presents complex examples, and summarizes the main topics.

Collections: Lists vs Sets

Explores the differences between lists and sets, emphasizing the challenges of defining equality.

Group Theory: Basics