Condensed-Algorithms/CS577Notes.toc at master · ChristianBorst/Condensed-Algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
\contentsline {section}{\numberline {1}Recurrence Relations}{3}
\contentsline {subsection}{\numberline {1.1}Recursive Analysis of Insertion and Merge Sort}{3}
\contentsline {subsection}{\numberline {1.2}Recursive Linear Selection}{3}
\contentsline {subsection}{\numberline {1.3}Recursive Quadratic Closest-Pair}{4}
\contentsline {subsection}{\numberline {1.4}Divide and Conquer Recurrences and Master Theorem}{4}
\contentsline {subsection}{\numberline {1.5}Asymptotics}{5}
\contentsline {section}{\numberline {2}Arithmetic Algorithms and Sorted Lists}{6}
\contentsline {subsection}{\numberline {2.1}Arithmetic Algorithms}{6}
\contentsline {subsection}{\numberline {2.2}Quicksort}{6}
\contentsline {subsection}{\numberline {2.3}Random Choices in Algorithms}{7}
\contentsline {subsection}{\numberline {2.4}Splay Trees}{7}
\contentsline {section}{\numberline {3}Data Structures and Algorithms}{10}
\contentsline {subsection}{\numberline {3.1}Graphs and Graph Traversal}{10}
\contentsline {subsection}{\numberline {3.2}Shortest Path Problems}{10}
\contentsline {subsection}{\numberline {3.3}Cycle Detection Problem}{11}
\contentsline {subsection}{\numberline {3.4}Sources and Sinks in Directed Acyclic Graphs}{11}
\contentsline {subsection}{\numberline {3.5}Self Organizing Lists}{12}
\contentsline {subsection}{\numberline {3.6}Union-Find Data Structure}{12}
\contentsline {section}{\numberline {4}NP-Complete Problems}{13}
\contentsline {subsection}{\numberline {4.1}NP-Complete Graph Problems}{13}
\contentsline {section}{\numberline {5}Dynamic Programming}{13}
\contentsline {section}{\numberline {6}Network Flow and Linear Programming}{14}
\contentsline {section}{\numberline {A}Review of Basic Mathematical Concepts}{15}
\contentsline {subsection}{\numberline {A.1}Properties of Logarithms}{15}