Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
19sts250 [2019-01-15] – [Transdisciplinary Data Structures (STS250) in Spring 2019 at KAIST] Martin Ziegler | 19sts250 [Unknown date] (current) – removed - external edit (Unknown date) 127.0.0.1 | ||
---|---|---|---|
Line 1: | Line 1: | ||
- | ====== Transdisciplinary Data Structures (STS250) in Spring 2019 at KAIST ====== | ||
- | Lecturer: Martin Ziegler | ||
- | |||
- | Schedule: Mondays and Wednesdays, 13:00 to 14:15 | ||
- | |||
- | ===== Synopsis/ | ||
- | STS250 conveys the mechanism of digital data processing | ||
- | that culminated in contemporary computing technology, | ||
- | ranging in transdisciplinary breadth from electrical signals | ||
- | via Boolean gates and circuits, data representation, | ||
- | basic operations, to the core of this course: | ||
- | data structures, their properties and algorithmic maintenance. | ||
- | |||
- | I. Mathematical and Boolean basics and circuits | ||
- | * induction, recursion, and recurrences | ||
- | * graph terminology and properties: directed acyclic | ||
- | * basis, addition, carry-look-ahead, | ||
- | 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, | ||
- | * 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/ | ||
- | * queue=FiFo, stack=LiFo | ||
- | * binary trees: terminology, | ||
- | VII. Basic Graph Problems and Algorithms | ||
- | * Un-/ | ||
- | * Shortest unweighted path: BFS | ||
- | * single source shortest weighted path: Dijkstra | ||
- | VIII. Abstract Data Types and their implementations | ||
- | * stack, queue, priority queue, dynamic array, … |