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 (28 aug - 29 aug)

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 (30 aug)

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

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

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

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

Pekare, länkade noder, länkade listor (OH-bilder, kod)
Extensible arrays, amortised analysis (OH-bilder, kod, , amortized-add-array-list.pdf)
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

Klasser, operatöröverlagring. (OH-bilder, kod)
Undantag, mallar, konstruktorer, implementation av en containerklass (OH-bilder, kod)
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

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

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

HT2
Föreläsning 13-14 (09 okt - 10 okt)

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 (2 nov - 6 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

Extra labb 2

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 12.1 12.2 12.3 12.4 12.5
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


 


Sidansvarig: Ahmed Rezine
Senast uppdaterad: 2023-11-14