Göm menyn

TDDD86 Datastrukturer, algoritmer och programmeringsparadigm

Föreläsningar

Preliminär föreläsningsplan. Oh-bilder och kod från föreläsningarna kommer att göras tillgängliga nedan i anslutning till respektive föreläsning.

HT1
Föreläsning 1 (31 okt - 01 sep)

Kursadministration. Introduktion till Programmeringsparadigmer (OH-bilder)
Wikipedia: programming paradigm
Inlämningsuppgift

OpenDSA: kapitel 0.1, 1.1, 2.1, 2.2, 2.3, 2.4, 2.5, 2.6, 2.7, 2.9

Föreläsning 2 (02 sep - 07 sep)

Introduction till C++, funktioner och parametrar, strängar, strömmar. (OH-bilder, notes, kod)
Lippman et. al: kapitel 1, 2, 3, 4, 5, 6 och 8.
C and C++ for Java Programmers
C++ and Java Syntax Differences Cheat Sheet
Comparison of Java and C++
C++ docs: string, cctype, ifstream, iomanip, sstream
Wikipedia: datastructure, collection, array, STL, dequeue
Start with Labb 1

Föreläsning 3 (07 sep)

Abstrakta datatyper (ADT); vector, grid, stack, kö, lista (OH-bilder, kod)
C++ stack, queue, deque, array, list, forward_list
Lippman et. al: kapitel 9
C++ docs: vector, stack, queue, deque, array, list, forward_list
Wikipedia: ADT, stack, queue, list

Föreläsning 4 (09 sep)

ADT set, map, iteratorer (OH-bilder, kod)
Lippman et. al: kapitel 3.4, 11.
C++ docs: set, map, multiset, multimap, unordered_set, unordered_map, unordered_multiset, unordered_multimap
Wikipedia: set, map
Start with Labb 2

Föreläsning 5 (14 sep)

Algoritmanalys, ordonotation (OH-bilder, addentum)
OpenDSA: kapitel 3.1, 3.2, 3.3, 3.4, 3.5, 3.6, 3.7, 3.8, 3.9, 3.10, 3.12, 3.13, 3.14, 3.15, 3.16.
Wikipedia: algorithm analysis, big-oh

Föreläsning 6-7 (18-21-23 sep)

Pekare, länkade noder, länkade listor (OH-bilder, kod)
Implementation av stack och kö (OH-bilder, kod)
OpenDSA: kapitel: 4.1, 4.2, 4.3, 4.4, 4.5, 4.6, 4.7, 4.8, 4.9, 4.10, 4.12, 4.13, 4.14
Lippman et. al: kapitel 2.3.2.
Wikipedia: pointer, linked list
Labb 3

Föreläsning 8-9 (28-30 sep)

Klasser, operatöröverlagring, dynamiskt minne. Amorterad analys. (OH-bilder, kod)
Undantag, mallar, konstruktorer, implementation av en containerklass (OH-bilder, kod, amortized.pdf)
OpenDSA: kapitel 3.11
Lippman et. al: kapitel 2.6, 3.5, 7, 12.1.2, 12.2.1, 13, 14, 16.1, 18.1
C++ docs: Classes, Templates, Exceptions, Dynamic memory
Wikipedia: operator overloading, templates

Föreläsning 10-11 (05-07 okt)

C++ arv, polymorfi (OH-bilder, kod)
STL algorithms, funktionsobjekt, lambdauttryck (OH-bilder, kod)
Lippman et. al: kapitel 10, 12.1, 14.8, 15 och 16.
C++ docs: Inheritance, Polymorphism, <algorithm>, <numeric>, <functional>
Wikipedia: inheritance, polymorphism
Labb 4

Föreläsning 12 (07-12 okt)

C++ som multiparadigmspråk (OH-bilder, kod)

HT2
Föreläsning 13-14 (2-3 nov)

Rekursion, komplexitetsanalys av rekursiva algoritmer (OH-bilder)
Rekursiv sökning, totalsökning, backtracking (OH-bilder, kod, extra läsning)
OpenDSA: kapitel 4.11
Wikipedia: recursion, binary search, brute-force search, backtracking
Labb 5

Föreläsning 15-17 (9-17 nov)

ADT Träd, binära sökträd, AVL-träd, B-träd (OH-bilder)
OpenDSA: kapitel 5.1, 5.2, 5.3
OpenDSA: kapitel 8.1, 8.3
OpenDSA: kapitel 6.1, 6.2, 6.3, 6.4, 6.5, 6.6, 6.7, 6.8, 6.9, 6.10, 6.11, 6.12
OpenDSA: kapitel 7.1, 7.2
7.3
OpenDSA: kapitel 9.1, 9.2, 9.3, 9.4, 9.5, 9.6
9.7, Splay-träd, Hashning, Skip-listor (OH-bilder)
OpenDSA: kapitel OpenDSA: kapitel 10.1, 10.2, 10.3, 10.4, 10.5, 10.6, 10.7, 10.8, 10.9, 10.10,
OpenDSA: kapitel 13.3, 13.4
Prioritetskö, Heap, Union/Find, Trie, geometriska tillämpningar av binära sökträd (OH-bilder)
OpenDSA: kapitel 8.2
OpenDSA: kapitel 6.13, 6.14, 6.15
6.16
6.17
C++ docs: priority_queue
Wikipedia: binary tree, BST, AVL tree, splay tree, B-tree, trie, hash table, skip list, priority queue, heap, disjoint-set data structure
Labb 6
Extra labb 1

Föreläsning 18-19

Sortering I. Insertion Sort, Selection Sort, Quick Sort, Selection/Median finding, Quickselect (OH-bilder)
OpenDSA: kapitel 11.1, 11.2, 11.3, 11.4, 11.5, 11.6, 11.7, 11.8
11.11
Sortering II. Heap Sort, Merge Sort, Undre gränser för sortering, Counting Sort, Bucket Sort, Radix Sort (OH-bilder)
OpenDSA: kapitel 11.9, 11.10, 11.12, 11.13, 11.14, 11.15
11.16, 11.17
Wikipedia: sorting algorithm, insertion sort, selection sort, merge sort, quicksort, selection algorithm, quickselect, comparison sort, counting sort, bucket sort, heapsort, radix sort
Labb 7

Föreläsning 20-21

Grafer, grafsökning (OH-bilder)
Riktade och viktade grafer (OH-bilder)
OpenDSA: kapitel 13.1, 13.2, 13.3, 13.4, 13.5, 13.6, 13.7, 13.8
Wikipedia: graph, dfs, bfs, adjacency list, adjacency matrix, Dijkstra's algorithm, A, Floyd-Warshall algorithm
Labb 8

Föreläsning 22-23

Metoder för algoritmdesign (OH-bilder)
Exempel gammal tenta 150824
OpenDSA: kapitel 14.1, 14.2, 14.3, 14.4, 14.5, 14.6, 14.7, 14.8, 14.9
Wikipedia: algorithm design, divide and conquer, dynamic programming, greedy algorithm, back tracking

Extra labb 2


 


Sidansvarig: Ahmed Rezine
Senast uppdaterad: 2020-11-16