Program Overview

Program Overview

The University of Copenhagen offers a course titled "Randomised Algorithms for Data Analysis (RAD)" as part of its Bachelor's program in Computer Science.

Course Description

Randomised algorithms are often superior to their traditional deterministic counterparts. Many computational problems are practically impossible without the use of randomisation. The course will cover application areas such as graph algorithms and large data streams relevant to machine learning and data analysis, with a focus on the fundamental understanding of using probabilities in algorithms and data analysis.

Learning Objectives

• Knowledge of: Relevant combinatorial probability theory and randomised techniques in algorithms, including variance and spread, tail probabilities, randomised data structures, and analysis of large data streams.
• Skills in: Showing bounds for the expected running time of randomised algorithms and explaining methods to limit the probability that a random variable deviates far from its expected value.
• Competencies in: Reasoning about and applying randomised techniques to data analysis problems, finding simple and effective randomised algorithms and data structures where traditional deterministic methods are more difficult or less effective.

Course Materials

The course materials are available on Absalon, with the expected textbook being "Randomized Algorithms" by Motwani and Raghavan.

Prerequisites

The recommended academic prerequisites include basic probability calculus corresponding to the course "Mathematical Analysis and Probability Theory in Computer Science" or "Mathematical Analysis and Statistics in Computer Science", as well as basic algorithmics corresponding to the course "Algorithms and Data Structures".

Teaching Methods

The course will be taught through lectures, exercises, weekly assignments, and an implementation project.

Workload

• Forelæsninger: 28 hours
• Forberedelse (estimated): 100 hours
• Teoretiske øvelser: 28 hours
• Øvelser: 24 hours
• Projektarbejde: 25 hours
• Eksamen: 1 hour
• Total: 206 hours

Assessment

The course assessment will be based on a written exam, with the possibility of individual or collective feedback during the course.

Examination

• The exam is a 30-minute oral exam with 30 minutes of preparation.
• The examination requirements include the submission and approval of the implementation project and 3 out of 4 written weekly assignments.
• All aids are allowed except Generative AI and internet access.
• The assessment form is a 7-point scale, with external censorship.

Re-examination

The re-examination follows the same format as the ordinary examination. Qualification for the re-examination is obtained by submitting and having approved the implementation project and 3 out of 4 weekly assignments no later than 2 weeks before the re-examination.

Course Information

• Language: Danish
• Course code: NDAB18001U
• Points: 7.5 ECTS
• Level: Bachelor
• Duration: 1 block
• Placement: Block 4
• Schedule group: C
• Course capacity: No limitation, unless you sign up in the late registration period (BA and KA) or as a merit or single-course student.

Study Board

The study board responsible for this course is the Study Board for Mathematics and Computer Science.

Offering Institute

The course is offered by the Department of Computer Science.

Offering Faculty

The course is part of the Faculty of Science.

Course Responsible

The course is managed by Jacob Holm.