Datastructures for IN
6 EC
Semester 1, periode 2
5061DAVI6Y
| Eigenaar | Bachelor Informatica |
| Coördinator | dr. Steven de Rooij |
| Onderdeel van | Bachelor Informatica, jaar 1Dubbele bachelor Wiskunde en Informatica, jaar 1Pre-master Software Engineering, jaar 1 |
| Links | Zichtbare leerlijnen |
Datastructuren en algoritmen vormen een hoeksteen van de informatica. Computers zijn gegevensverwerkende machines; in deze cursus wordt onderzocht hoe de data in het computergeheugen kan worden georganiseerd zodat efficiënte verwerking mogelijk wordt.
De cursus omvat concepten die uiteenlopen van heel concreet tot behoorlijk abstract. Aan de concrete kant kijken we naar basale computerarchitectuur en de consequenties daarvan voor efficiënt programmeren. We gebruiken de programmeertaal C omdat dit goede controle biedt over de manier waarop data in het geheugen worden opgeslagen. We kijken ook hoe je de efficiëntie van een algoritme kunt meten.
Je leert ook de meest belangrijke datastructuren kennen, zoals arrays, lijsten, bomen, hash tables, en heaps.
Aan het meer abstracte uiteinde zul je leren onderscheid maken tussen datastructuren en abstracte datatypes, we onderzoeken hoe je kunt bepalen hoeveel tijd en geheugen zal worden gebruikt door een algoritme, op basis van de programmacode, en hoe je je bevindingen kunt samenvatten met grote O notatie. We zullen het hebben over best case, average case en worst case tijdcomplexiteit, en we zullen amortized analyse gebruiken voor operaties die "meestal snel maar soms langzaam" zijn.
Suggestions for optional additional reading are provided in the first lecture.
De hoorcolleges 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.
|
Activiteit |
Uren |
|
|
Digitale Toets |
2 |
|
|
Hoorcollege |
28 |
|
|
Laptopcollege |
28 |
|
|
Zelfstudie |
110 |
|
|
Totaal |
168 |
(6 EC x 28 uur) |
Aanvullende eisen voor dit vak:
Aanwezigheid op de practica is verplicht. Afwezigheid bij meer dan vier practica kan uitsluiting van het hertentamen tot gevolg hebben.
| Onderdeel en weging | Details |
|
Eindcijfer | |
|
1 (100%) Tentamen digitaal |
Zowel het examencijfer als het practicumcijfer moeten minstens 5 zijn. In dat geval is je eindcijfer het gemiddelde van de twee cijfers. Het eindcijfer moet minstens 5.5 zijn om voor de cursus te slagen.
Benader de practicumassistenten voor vragen over de beoordeling van de practicumopdrachten.
Een inzagemoment voor het tentamen wordt via Canvas bekend gemaakt op het moment dat de resultaten gepubliceerd worden.
Er zijn vijf programmeeropdrachten. Het beoordelingsschema staat telkens aangeduid in de opdracht. Let op: de rubric is niet precies gelijk aan die bij Inleiding Programmeren.
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
De planning wordt bijgehouden op Canvas.
Steven de Rooij / s.derooij@uva.nl