This is an old revision of the document!
Transdisciplinary Data Structures (STS250) in Spring 2019 at KAIST
Synopsis/Syllabus:
I. Mathematical and Boolean basics and circuits * induction, recursion, and recurrences * graph terminology and properties: directed acyclic * basis, addition, carry-look-ahead, multiplication, MUX
II. Basic mathematical data types and operations
- boolean, non-negative integer, integer, character
- representation in digital computer
- algorithmic primitives
III. Combining mathematical data types
- tuple, finite sequence, un/directed labeled graph
- representation in digital computer
IV. Computational problems and algorithmic solutions
- polynomial multiplication, matrix multiplication
- asymptotic growth, recurrences and their solutions
V. Searching and Sorting
- linear search, binary search, bubble sort, bucket sort
- specification and analysis of the above algorithms
- mergesort, quicksort, linear-time median
- lower bound for comparison-based sorting
VI. Linked Data Structures
- lists: singly/doubly-linked; search/traverse, insert/delete
- queue=FiFo, stack=LiFo
- binary trees: terminology, BFS/DFS/search, insert/delete/balance
VII. Basic Graph Problems and Algorithms
- Un-/directed graph terminology and properties
- Shortest unweighted path: BFS
- single source shortest weighted path: Dijkstra
VIII. Abstract Data Types and their implementations
- stack, queue, priority queue, dynamic array, …