Home/Syllabus

Schedule/Notes

Topics

Topics

Git & Github || Java (the basics)

Fundamental Data Structures

• Lists, Stacks, and Queues
• Binary Trees
• Heaps
• Huffman Coding Tree
• Non-Binary Trees

Sorting and Searching

• Sorting: Mergesort; Quicksort; Heapsort
• Searching: Hashing
• Indexing

Graphs

• Graph Traversals: DFS, BFS, Topological Sort and applications (e.g., finding connected components and articulation points)
• Shortest-Path Problems (Dijkstra's algorithm)
• All-Pairs Shortest Paths (Floyd's algorithm, a DP Algorithm)
• Minimum-Cost Spanning Trees (Prim's and Kruskal's algorithm)

Advanced Tree Structures

• Tries
• 2-3 tree; B-tree; B⁺-trees; B^*-trees; AVL tree, [Splay tree], K-D tree
• Suffix Tree & Suffix Array for String Matching

Algorithms

• Greedy Algorithm (Huffman Tree Building & Minimum-Cost Spanning Trees)
• Dynamic Programming Algorithm (Edit distance; 0-1 knapsack problem; shortest-Path Problem & DNA Sequence Alignment); All-Pairs Shortest Paths (Floyd's algorithm, a DP Algorithm)

Applications

• Bioinformatics
• The codon table -- a dictionary for translating nucleic acid sequences to protein sequences.
• Searching for similar sequences: from edit distance to more advanced algorithms using all kinds of smart data structures and indices
• Compression of sequences: go beyond Huffman coding
• Tree structures in bioinformatics: tree of life
• Graphs are everywhere in bioinformatics
• Data Mining in Social Networks
• Analysis of tweets
• Data mining of social networks represented as graphs

Advanced Data Structures & topics (for H343)

• Memory hierarchy; data structures optimized for external memory; and cache-oblivious data structures. Any problem (e.g., sorting, priority queues) is different when you're dealing with disk instead of main memory, or you care about cache performance.