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 (02 sep - 04 sep)
Kursadministration. Introduktion till Programmeringsparadigmer (OH-bilder, kod))
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 (04 sep - 06 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 (09 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 (12 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 (16 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 - 25 sep)
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
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
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
|
English web site
