30 Oct 2018
Djikstra’s algorithm: determine shortest paths between nodes in graph with edges of different lengths.
Data structures
Purpose is to organize data so that it can be accessed quickly and usefully. Different data structures support different sets of operations, and are thus suited for different problems.
E.g., a queue is great for breadth first search whereas a stack is better for depth first search.
In general, the fewer set of operations that a data structure supports, the faster it will be. Thus, you should usually select the ‘minimal’ data structure that fits your problem for maximum performance. Worth remembering is that though two data structures might both be O(log(n)) in time (for example), the constants not included in the Big-O score can still mean one is considerable faster than the other.
More …
27 Oct 2018
Goals:
- Find everything findable from a given start vertex
- Don’t explore anything twice
Generic Algorithm
Given graph G, vertex s.
- Mark Initial s explored, all other vertices unexplored
- While possible:
- Choose an edge (u, v) with u explored and v unexplored
- mark v explored
More …
25 Oct 2018
Finishing up list ordering with some search, and then moving on to some initial graph theory. Not much of note, though the quizz proved quite tricky this week.
More …
23 Oct 2018
Week 2 discusses the Master Method and QuickSort. My notes focuses on the former.
What: Black box algorithm used to analyze recursive algorithms.
Assumption: All subproblems have equal size.
More …
18 Oct 2018
Going through the self paced course Algorithms: Design and Analysis, given by Stanford.
The first week included a course introduction, Big-O notation and a programming assignment including the implementation of the MergeSort algorithm (my code can be found here).
“Perhaps the most important principle for the good algorithm designer is to refuse to be content.”
(Aho, Hopcroft, and Ullman, The Design and Analysis of Computer Algorithms, 1974)
I.e.; can we do better?
More …