oskarth / dsa Goto Github PK

Data models: tree, list, set, relational (?), graph

wc -l *.c *.h => 358

array, list, bst, hashmap

a dictionary supports insert, delete, lookup

...linear and binary search in array

dynamic programming algo: longest common substring, LCS. ?

character strings lists...?, null character

for hash maps - impl dict, that is: insert delete lookup

trees - generalize with LCRS tree, pointer to leftmost child and right sibling.

trees - preinpostorder as arithmetic expressions, in: a + (b-c)d, (+ a ( (- b c) d)), '3 4 +' reverse polish notation

bsts as dictionaries (adt)

so you can implement it, fine. but how do you know it works, and its complexity? test data, measure. testing and measuring a must.

also grok inorder postorder thingies.

interface in header, only public things, rest static.

whats up with extern?

all header files sub 20, all impls sub 100, that's 500 locs, then some tests/docs

// motivating problem: make a (name, value) table using arrays // operations to implement // how would you test it? // how would you measure it to find bottlenecks?

dynamic array: (name, value) table with add and delete linked list: (name, value) table with create, add, lookup, apply

algo design manual notes priority queue sup? sorting helps access etc, couple of ex, data struct techniques, divide-and-conquer, randomization (qsort), explain: linear and binary search (quintessential), graphs very universal, we restrict down to trees etc with terminolgoy, adjacency list most useful, BFS/DFS to visit every edge/vertex, standard graph also: MST, shortest path (hm...), simulated annealing heuristic searches sup?, caching for recursion calls (fib), dynamic programming understand,

• Measure, cool graph of hash table perf depending on key

• Test data, something like (wrong example but principle): while (scanf ("%s %d", name, &value) != EOF) {  p = newitem(name, value); lsit1 = addfront(list1, p); list2 = addend(list2,p); } for (p = listl; p != NULL; p = p->next) printf ("%s %d\nW, p->name, p->value);

• assert, check check error returns

• test incrementally, and simple parts

• scaffold testing to mechanize it, read from input file

• test automation

• measure:

• use a profiler
• focus on hot spots
• draw a picture

http://www.lysator.liu.se/c/pikestyle.html http://www.cs.princeton.edu/courses/archive/spr11/cos217/lectures/08DsAlg.pdf http://cm.bell-labs.com/cm/cs/tpop/toc.html

http://sist.sysu.edu.cn/~isslxm/DSA/textbook/Skiena.-.TheAlgorithmDesignManual.pdf

/* data structures and algorithms to know by heart

dynamic array linked list binary tree hash table

linear and binary search DFS, pre-order and post-order BFS

quicksort

how to implement graphs, stacks and queues

// two things oskar // one, print this // two, try to seperate into different files // three, three things oskar // three, implement them, enough yak-shaving already */