Datastructuren voor IN

Datastructures for IN

Studiewijzer 2023/2024

Globale inhoud

Data structures and algorithms are a cornerstone of academic computer science. Computers are data processing machines; this course investigates the several ways in which the data can be laid out in the computer memory such that efficient processing becomes possible.

The course bridges concepts from the very concrete to the very abstract. On the very concrete end we review basic computer architecture and discuss the consequences of this architecture on programming. We adopt the programming language C since it provides good control over the way data are laid out in the computer memory. We also look at how to measure the efficiency of an algorithm.

On the middling level of abstraction you will learn to implement the most important data structures, including arrays, lists, trees, hash tables and heaps.

On the more abstract end we differentiate between data structures and abstract data types, we'll work out how to determine the resources used by a computer algorithm from the program itself, and how to summarise our findings using big O notation. We will discuss best case, average case and worst case time bounds, and how one might give lower or upper bounds for each of these, and we'll use amortized analysis for operations that are "usually fast but sometimes slow".

Studiemateriaal

Literatuur

• Suggestions for optional additional reading are provided in the first lecture.

Leerdoelen

• Implementeren van fundamentele datastructuren en algoritmen in C
• Het resourcegebruik van een algoritme analyseren met grote O notatie
• Het verschil kennen tussen worst case, best case, upper bound en lower bound
• Uitleggen hoe een datastructuur in het geheugen wordt opgeslagen

Onderwijsvormen

• Hoorcollege
• Laptopcollege

The lectures lay the theoretical groundwork for designing and analysing the most important data structures. This is tested via an online exam at the end of the course. A separate set of lectures teaches the C programming language, which is required for the practical sessions.

During the computer labs, students practice implementing these data structures by themselves, and experience firsthand the technicalities involved.

Verdeling leeractiviteiten

Aanwezigheid

Aanwezigheidseisen opleiding (OER-B):

• Voor practica en werkgroepbijeenkomsten met opdrachten geldt in principe een aanwezigheidsplicht. Wanneer studenten niet voldoen aan deze aanwezigheidsplicht kan dit als gevolg hebben dat het onderdeel niet met een voldoende kan worden afgerond.
  

Toetsing

Both the grade for the exam and your average on the computer labs has to be at least 5. In that case, your final grade is the average of both partial grades. You need a final grade of at least 5.5 to pass the course.

Inzage toetsing

For enquiries about the grading of the practical assignments the students can contact the TA team.

For feedback on the exam assessment, contact the coordinator by email.

Opdrachten

There are five graded programming assignments. Each has to be submitted, strictly before the deadline, and individually. Code may not be shared, but more general information and questions can be exchanged (for example, via the Canvas conference section).

Your work is scanned for plagiarism; in case there are questions you may be asked to explain your work. Since grading is automatic, you will receive feedback online and immediately.

Fraude en plagiaat

Over het algemeen geldt dat elke uitwerking die je inlevert ter verkrijging van een beoordeling voor een vak je eigen werk moet zijn, tenzij samenwerken expliciet door de docent is toegestaan. Het inzien of kopiëren van andermans werk (zelfs als je dat hebt gevonden bij de printer, in een openstaande directory of op een onbeheerde computer) of materiaal overnemen uit een boek, tijdschrift, website, code repository of een andere bron - ook al is het gedeeltelijk - en inleveren alsof het je eigen werk is, is plagiaat.

We juichen toe dat je het cursusmateriaal en de opdrachten met medestudenten bespreekt om het beter te begrijpen. Je mag bronnen op het web raadplegen om meer te weten te komen over het onderwerp en om technische problemen op te lossen, maar niet voor regelrechte antwoorden op opgaven. Als in een uitwerking gebruik is gemaakt van externe bronnen zonder dat een bronvermelding is vermeld (bijvoorbeeld in de rapportage of in commentaar in de code), dan kan dat worden beschouwd als plagiaat.

Deze regels zijn er om alle studenten een eerlijke en optimale leeromgeving aan te kunnen bieden. De verleiding kan groot zijn om te plagiëren als de deadline voor een opdracht nadert, maar doe het niet. Elke vorm van plagiaat wordt bestraft. Als een student ernstige fraude heeft gepleegd, kan dat leiden tot het uitschrijven uit de Universiteit. Zie voor meer informatie over het fraude- en plagiaatreglement van de Universiteit van Amsterdam: www.student.uva.nl

Weekplanning

Contactinformatie

Coördinator

• dr. Steven de Rooij

Coordinator: Steven de Rooij / s.derooij@uva.nl

Docent C: Simon Polstra / s.polstra@uva.nl