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

Taught in

Dutch

Faculty

Faculty of Sciences and Bioengineering Sciences

Department

Computer Science

Educational team

Wolfgang De Meuter (course titular)
Jens Nicolay

Activities and contact hours

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

Course Content

PREREQUISITES

In the course series "Algorithms and Data Structures 1&2", 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.

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

Course text (Required) : Algorithms and data structures in scheme (part 1), De Meuter, VUB, 2220170000206, 2015
Handbook (Recommended) : Introduction to Algorithms, Cormen, Leiserson, 3de, Rivest; MIT Press, 9780262033848, 2009
Handbook (Recommended) : Garbage Collection, Algorithms for Automatic Dynamic Memory Management, Jones, Lins, John Wiley & Sons, 9780471941484, 1996
Handbook (Recommended) : Database System The Complete Book, Garcia-Molina, Ullman, Widom, 2de, Pearson, 9781292024479, 2013

Additional info

A text entitled "Algorithms and Data Structures in Scheme" is made available on the learning platform. Additional reading can be found in the books "Introduction to Algorithms" (by Cormen, Leiserson, Rivest, MIT Press, 1991), "Garbage Collection: Algorithms for Automatic Dynamic Memory Management" (by Jones, Lins; John Wiley & Sons; 1996) and "Database System Implementation" (by Garcia-Molina, Ullman, Widom; Prentice-Hall, 2000).

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:
Oral Exam determines 50% of the final mark.
Written Exam determines 50% of the final mark.

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

examen mondeling with a relative weight of 1 which comprises 50% of the final mark.

Note: Het examen bestaat uit een schriftelijk en een mondeling gedeelte. Beide delen zijn even belangrijk in de eindevaluatie. Tijdens het academiejaar worden een aantal taken opgegeven die verplicht opgelost dienen te worden en meetellen in de eindbeoordeling.

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

examen schriftelijk with a relative weight of 1 which comprises 50% of the final mark.

Note: Het examen bestaat uit een schriftelijk en een mondeling gedeelte. Beide delen zijn even belangrijk in de eindevaluatie. Tijdens het academiejaar worden een aantal taken opgegeven die verplicht opgelost dienen te worden en meetellen in de eindbeoordeling.

Additional info regarding evaluation

The exam consists of a written and an oral part. Both parts have an equal weight in the final mark. A number of compulsory assignments are also taken into account. Absence in one of these constituents implies absence for the entire course.

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