Algemene informatie
Discrete Structures is een rare naam – het zou logischer zijn Discrete Wiskunde te heten. Dit betekent in feite wiskunde die niet continu is (d.w.z. calculus).
Voorwaarden
Neen
Onderwerpen
- Verzamelingen, functies, relaties
- Bewijstechnieken, inductie
- Numer theory and public key encryption
- Counting and combinatorics
- Probability
- Logic
- Graph Theory
- Finite automata and regular languages
- Context-vrije talen
- Computability and NP-CompletenessVeel tijd besteed aan bewijzen en nadruk op bewijzen door inductie.
Werklast
Normaal zijn er wekelijkse probleemreeksen, 2-3 voorrondes, en een finale. Historisch gezien is het huiswerk een relatief groot deel van het cijfer. Er is geen programmering in de cursus en de werklast is redelijk consistent gedurende het semester. Het is niet erg zwaar, maar kan een paar uur per week in beslag nemen, afhankelijk van hoe goed je de onderwerpen begrijpt.
Algemeen advies
Het volgen van deze cursus tegelijk met CS 2110 is zeer beheersbaar en nuttig. Er is veel overlap in de onderwerpen, vooral met betrekking tot bewijzen door inductie en grafentheorie (hoewel de overlap de laatste tijd minder is geworden, vooral omdat 2110 zich minder op bewijzen is gaan richten) en het is nuttig om de informatie twee keer te zien. Deze cursus is een basis voor veel CS, dus het is goed om hem redelijk vroeg te volgen. Het leren van grafentheorie en bewijzen is redelijk belangrijk voor veel hogere cursussen en algemene CS.
Ik vond het aanbevolen/vereiste tekstboek erg nuttig! Veel onderwerpen die in de les kort werden behandeld, werden in het tekstboek diepgaand behandeld. Het lezen van het tekstboek en het bekijken van de voorbeelden heeft mijn scores op de test verbeterd. Ook hoefde ik niet naar de kantooruren te gaan, die meestal erg druk waren.
Koop het tekstboek niet.
Zoek uit wie van de TA-studenten wiskunde majors zijn en vraag hen om hulp. Zij weten meer. 2800 is een theorieles, dus wiskundigen weten hier veel meer van dan CS-ers. Ook, zoals eerder gezegd, grafentheorie, bewijzen, en de meeste van de andere stof die je leert is zeer nuttig voor het redeneren over verschillende problemen.
Testimonials
Met Bart Selman, ik dacht dat deze klasse was echt makkelijk. Als je vóór deze cursus al enige ervaring met de onderwerpen hebt (wiskunde op de middelbare school en/of andere CS-lessen, zoals CS 1114), zou je in staat moeten zijn om minimale tijd aan deze cursus te besteden.
Ik was erg betrokken bij wiskunde op de middelbare school en deed wat getaltheorie/combinatoriek, en deze cursus ging niet verder dan dat. Ik heb tegelijkertijd MATH 3360 gedaan, wat in feite een veel moeilijkere versie van deze cursus is, dus ik heb uiteindelijk bijna niets geleerd in 2800.
Gedaan met een voldoende. Dit vak was een lachertje en ik heb weinig nieuwe stof geleerd, maar het was wel een goed overzicht van alle willekeurige wiskunde die ik meestal niet eerder officieel in mijn lessen had gezien. Weinig onderhoud en interessant genoeg.
Met Kozen (herfst 2013) was de cursus niet verschrikkelijk moeilijk, maar was moeilijker dan de andere getuigenissen je zouden doen geloven. We hadden 8 probleemsets in de loop van het semester, die elk meerdere uren in beslag namen. De examens waren redelijk van moeilijkheidsgraad, maar de voorrondes in de klas waren moeilijk af te werken in de gegeven tijd. (Er was genoeg tijd voor de finale.) Realiseer je dat je veel van de onderwerpen voor het eerst zult zien, tenzij je al een discrete wiskundeles hebt gevolgd.
Kozen (herfst 2013): Kozen was een zeer goede docent en legde alles in detail uit. Het probleem was dat hij veel meer in detail ging dan een breedte-les zou moeten doen, dus we leerden heel snel een heleboel verschillende onderwerpen met een behoorlijke diepgang. Nog steeds niet te moeilijk, maar dat betekende wel veel stof en veel details om te onthouden voor examens (bovenstaande getuigenis legt dit goed uit). De cursusaantekeningen van Pass (zie link hieronder) waren zeer nuttig, maar Kozen behandelde enkele andere onderwerpen. Het boek was niet al te nuttig, maar je had het wel nodig omdat een paar problemen uit het boek kwamen.
Graeme Bailey (voorjaar 2014): We waren in voor een behoorlijke verrassing. Hoewel deze klas de reputatie heeft relatief makkelijk te zijn, was het materiaal dit semester erg moeilijk. Naast de gebruikelijke onderwerpen, besteedde Bailey een groot deel van de tijd aan verschillende abstracte algebra onderwerpen, met name groepentheorie. Ongeveer 35% van de studenten zakte binnen de deadline.
Wekelijkse huiswerkopdrachten werden meestal op woensdag vrijgegeven en moesten de maandag daarop worden ingeleverd (we kregen 10 dagen de tijd, maar kregen er zelden meer dan 5). Ze waren zeer bewijs intensief en namen een aanzienlijke 10-15 + uur van de tijd. Afgezien van de weinige wiskunde majors, waren de meeste TA’s niet in staat om te helpen met de huiswerken, omdat ze niet wisten hoe ze de problemen zelf moesten maken, en brachten ze hun kantooruren door met ons te spartelen.
Hoe dan ook, Bailey deed een merkbare inspanning om zijn studenten te helpen, door extra kantooruren aan te bieden en snel te reageren op Piazza. Tests werden ofwel in de klas of ’s avonds aangeboden, en waren verrassend eerlijk. Afsluitende opmerkingen: Kwam levend uit deze klas, deed er veel meer moeite voor dan ik wilde, leerde waarschijnlijk veel over discrete wiskunde, maar zou een gemakkelijkere professor nemen als ik kon.
George (voorjaar 2020): Ik persoonlijk heb echt genoten van deze les en vond het materiaal interessant, maar YMMV. Werklast was beheersbaar, maar je had vrij veel kantooruren nodig (die heel laat ’s avonds werden gehouden pre-COVID) om het goed te doen. Tweewekelijkse probleem-sets werden vrijgegeven tussen maandag en woensdag en moesten de vrijdag van de volgende week ingeleverd worden, en je kon er met een partner aan werken. Voor colleges (pre-COVID) werden we verondersteld de “prep” op de wiki voor de les te lezen, en tijdens de les deden we vooral voorbeelden en iClicker-vragen om het concept te versterken. In de colleges na het online gaan leerden we meer van de stof tijdens het college zelf. Over het geheel genomen een vrij moeilijk college, maar de moeite waard als je het eenmaal hebt afgerond.
Vorige aanbiedingen
Hopcroft geeft dit meestal in de herfst en Pass, in de lente. Kozen geeft deze les in de herfst van 2013. Michael George nam het over in het najaar van 2014. Anke van Zuylen zal dit onderwijzen vanaf Herfst 2020.