5 ECTS credits
150 h study time

Offer 1 with catalog number 1015254ANW for working 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
Registration for this course is allowed if one is registered for or has successfully accomplished "Structure of Computerprograms I". PLEASE NOTE: In addition, only students who are registered as working students or who have been authorized to attend the classes specifically organized for working students can register for this course offering. Regular students cannot register for the classes that are part of this course offering, they can only attend classes of course offerings with a course catalogue number ending in R. If you have any questions or encounter problems, please contact the Student Administration Centre through SAC@vub.ac.be.
Taught in
Dutch
Faculty
Faculty of Sciences and Bioengineering Sciences
Department
Computer Science
Educational team
Wolfgang De Meuter (course titular)
Activities and contact hours

26 contact hours Lecture
26 contact hours Seminar, Exercises or Practicals
125 contact hours Independent or External Form of Study
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) : Database System The Complete Book, Garcia-Molina, Ullman, Widom, 2de, Pearson, 9781292024479, 2013
Handbook (Recommended) : Garbage Collection, Algorithms for Automatic Dynamic Memory Management, Jones, Lins, John Wiley & Sons, 9780471941484, 1996
Handbook (Recommended) : Introduction to Algorithms, Cormen, Leiserson, 3de, Rivest; MIT Press, 9780262033848, 2009
Additional info

A text entitled "Algorithms and Data Structures in Scheme" is made available on the Pointcarré system. 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 45% of the final mark.
Written Exam determines 45% of the final mark.
PRAC Report determines 10% of the final mark.

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

  • Mondeling examen with a relative weight of 45 which comprises 45% of the final mark.

    Note: Het examen bestaat uit een schriftelijk en een mondeling gedeelte. Beide delen zijn even belangrijk in de eindevaluatie.

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

  • Schriftelijk examen with a relative weight of 45 which comprises 45% of the final mark.

Within the PRAC Report category, the following assignments need to be completed:

  • Taken with a relative weight of 10 which comprises 10% of the final mark.

    Note: 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

This offer is part of the following study plans:
Bridging Programme Master of Science in Applied Sciences and Engineering: Computer Science: Standaard traject (only offered in Dutch)
Bridging Programme Master of Science in Applied Computer Science: Standaard traject (only offered in Dutch)
Preparatory Programme Master of Science in Applied Sciences and Engineering: Computer Science: Standaard traject (only offered in Dutch)
Preparatory Programme Master of Science in Applied Computer Science: Enkel voor studenten industriële wetenschappen (only offered in Dutch)
Preparatory Programme Master of Science in Applied Computer Science: Preparatory programme Toegepaste Informatica (only offered in Dutch)