Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
19sts250 [2019-02-24] – [Transdisciplinary Data Structures (STS250) in Spring 2019 at KAIST] Martin Ziegler19sts250 [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 
- 
-Location: N1 #112 
- 
-Language: English 
- 
-Grading: Homework 30%, Attendance/quizzes 10%, Midterm exam 30%, Final exam 30%. 
- 
-Midterm exam on Monday, April 15 at 13h00, \\ 
-Final exam on Monday, June 10 at 13h00. 
-===== Synopsis/Syllabus: ===== 
-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, 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, …