Algorithms and Data Structures 1

6 ECTS credits
150 h study time

Offer 1 with catalog number 1015259ANR for all students in the 1st semester at a (A) Bachelor - preliminary level.

Semester

1st semester

Enrollment based on exam contract

Impossible

Grading method

Grading (scale from 0 to 20)

Can retake in second session

Yes

Enrollment Requirements

'Algorithms and Data Structures 1' means that students bachelor computer science and bachelor artificial intelligence simultaneously follow 'Structure of Computer Programs I' or have successfully passed 'Structure of Computer Programs I'. 'Algorithms and Data Structures 1' means that students bachelor mathematics and data science simultaneously follow 'Higher-Order Programming' or have successfully passed 'Higher-Order Programming'.

Taught in

Dutch

Faculty

Faculty of Sciences and Bioengineering Sciences

Department

Computer Science

Educational team

Jens Nicolay (course titular)

Activities and contact hours

26 contact hours Lecture
26 contact hours Seminar, Exercises or Practicals

Course Content

PREREQUISITES

In the course a number of algorithms is presented that belong to the basic vocabulary of a computer scientist. In principle, the algorithms and data structures are independent of any specific programming language. However, for the sake of scientific precision, we use Scheme as the formal language of expression.

CONTENTS

This course covers the following subjects:

- Data abstraction and procedural abstraction: Data constructors, Abstract Data Types (ADTs), Genericity, Execution time of algorithms (big O, Theta and Omega notation).

- Pattern Recognition: Brute-Force, Knutt-Morris-Pratt, the Sunday Quicksearch algorithm.

- Linear data structures: Vectorial lists, single linked lists, double linked lists, searching in linear data structures, rings,

- Linear ADTs: stacks, queues, priority queues, heaps.

- Sorting: Taxonomy of Sorting, Simple sorting algorithms (bubble sort, insertion sort and selection sort), Advanced Sorting Techniques (Quicksort, heapsort, merge sort), Linear Sorting Techniques (radix sort, counting sort, bucket sort), Theoretical Lower Bound on Sorting.

- Trees with applications: Dictionaries, Traversing Trees, Binary Search Trees, AVL Trees, Balancing.

- Hashing: Devising Hash functions, Primary and Secondary Clustering, Collision Resolution Strategies (external chaining, open addressing), Rehashing (linear, double, quadratic).

Course material

Digital course material (Required) : Lecture slides and course text, Available on Canvas

Additional info

n.a.

Learning Outcomes

General competencies

Knowledge and Understanding: An important part of this course consists of conveying encyclopaedic knowledge: students are required to know the name of the algorithms and data structures, are required to understand their inner workings and implementations, and are required to be able to evaluate their applicability in a particular situation. A lot of attention is devoted to estimating performance characteristics of algorithms and implementations of the operations that operate on a data structure. Students have to be able to evaluate and compare implementations of abstract data types that use alternative algorithms.

Application of Knowledge and Understanding: A second goal consists of applying that knowledge to concrete situations. Students should be capable of adjusting existing algorithms and ADT implementations to satisfy new constraints. They have to be able to design new ADTs for a given application and they have to be capable of selecting the correct algorithms and data structures in order to implement those ADTs.

Making Judgements: Students should be able to evaluate and compare existing algorithms, data structures and ADT implementations. Additionally, after completing the course, students should be able to make judgements about the quality of the implementation of an algorithm or the operations of a data structure.

Communication: Students are taught to communicate precisely about the functionality of an ADT by describing it using a formal ADT notation. The goal is to teach the communication between several developers in a project.

Learning Skills: The taxonomy presented by the course is supposed to give students a structural insight in order for them to be able to recognize and look up variations of the material studied in the literature.

Grading

The final grade is composed based on the following categories:
Written Exam determines 100% of the final mark.

Within the Written Exam category, the following assignments need to be completed:

Written exam with a relative weight of 1 which comprises 100% of the final mark.

Additional info regarding evaluation

During the course of the semester, tasks and exercises must be submitted to the grading platform used by the course. The precise details and deadlines will be published on Canvas. 5% of the final grade of the course is determined by the level of participation as well as the correctness of the solutions submitted on this platform. The remaining 95% of the final grade is determined by the written exam on theory and exercises.

In the 2nd examination period, the written exam determines the entire final grade.

Allowed unsatisfactory mark

The supplementary Teaching and Examination Regulations of your faculty stipulate whether an allowed unsatisfactory mark for this programme unit is permitted.

Academic context