CMU 15-445 Database Systems Lecture #01: Course Overview & Relational Model Outline Course Logistics Relational Model Relational Algebra Course overiew This course is about the design/implementation of database management systems (DBMSs) This is not a course ($\rightarrow Key\ point\ is\ the\ theory\ and\ the\ concept$) about how to use a DBMS to build applications or how to administer a DBMS.→ See CMU 95-703 (Heinz College) PROJECTS All projects will use the CMU DB Group BusTub academic DBMS.
Operating System $Nanjing\ University\rightarrow Yanyan\ Jiang\newline$ 多处理器编程：从入门到放弃 Overview 复习 程序 (源代码S、二进制代码C) = 状态机 编译器 $C = \textrm{compile}(S)\newline$ 应用视角的操作系统 = syscall 指令 本次课回答的问题 Q: 在
Operating System $Nanjing\ University\rightarrow Yanyan\ Jiang\newline$ 操作系统上的程序 Overview 复习 什么是操作系统？ 应用视角 (设计): 一组对象 (进程/文件/…) + API 硬件视角 (实现): 一个 C 程序
Operating System $Nanjing\ University\rightarrow Yanyan\ Jiang\newline$ 操作系统概述 $Overvier\newline$ 为什么要学操作系统? $(why)\newline$ 到底什么是操作系统? $(what)\newline$ 怎么学操作系统? $(how)\newline$ 为什么学操作系统?$(why)\newline$ 每天
Data Structure Sorting QuickSort Idea $Process\ after\ dividing \rightarrow$(like MergeSort in thought)
Divide the sequence into two subsequences $$ S=S_L+S_R $$ Downsizing $$ max(|S_L|,|S_R|) < n $$ Be independent of each other $$ max(S_L) \leq min(S_R) $$ After the subsequences are sorted recursively, the original sequence is ordered naturally $$ Sorted(S)=Sorted(S_L)+Sorted(S_R) $$ A trivial solution: With a single element, is itself a solution$\rightarrow Recursive\ base\newline$
Problem How to delimit subsequence?
Data Structure Searching Read Map Static Search Table Sequential Search Binary Search Indexing Search Binary Search Trees (Dynamic Search Table) Binary search tree AVL tree B-Tree Hash Table What is hashing Hash Function Collision Resolution Closed Hashing Open Hashing Analysis of Hashing Search Table Definition A set of the same type of data elements Key The value of data item in the data element. It is used to identify the
Data Structure Graph Definition: A graph G consists of two sets
a finite, nonempty set of vertices V(G)
a finite, possible empty set of edges E(G)
G(V,E) represents a graph
The number of vertices is written $|V|(n)$, and the number of edges is written $|E|(e)$
General graphs differ from trees
need not have a root node no implicit parent-child relationship may be several (or no) paths from one vertex to another Definition For a Directed graph $if\ u, v\ are\ two\ vertices,then\ <u, v> is\ an\ arc(edge), u\ is\ called\ as\ tail, v\ is\ called\ head$
Something About Dynamic Programming $Fibonacci\ By\ Dynamic\ Programming$ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 /* * In this program, we will calculate the Fibonacci by dynamic programming * The definition of the Fibonacci: Fibonacci(n) = Fibonacci(n - 1) + Fibonacci(n - 2) (n >= 2) * Fibonacci(1) = 1 and Fibonacci(0) = 0 * we can find the program is faster than the recursion's * T(n) = O(n) and S(n) = O(1) */ #include <iostream> std::size_t FibonacciByDynamicProgramming(std::size_t n) { std::size_t f{0}, g{1}; for (std::size_t i = 0; i < n; i++) { g = g + f; f = g - f; } return f; } int main() { for (std::size_t i = 0; i <= 64; i++) std::cout << "Fibonacci(" << i << ") = " << FibonacciByDynamicProgramming(i) << std::endl; return 0; } $Longest\ Common\ Subsequence\ By\ Dynamic\ Programming$ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 /* * In this program, we will use dynamic programming to find the length * of the longest common subsequence in two arrays * T(m + n) = O(m * n) and S(m + n) = O(m * n) */ /* * Example: array1[] = {1, 2, 3, 4, 5, 6, 7} * array2[] = {2, 5, 6, 7} * we should make a matrix(n * m) and make the element in array1 and array2 in the top and left of the matrix * like this case: 1 2 3 4 5 6 7 * 2 0 0 0 0 0 0 0 * 5 0 0 0 0 0 0 0 * 6 0 0 0 0 0 0 0 * 7 0 0 0 0 0 0 0 * Then we will fill the matrix top line and leftest column * The measuring of the matrix[1, x] x -> [1, m]: * The length of the longest common subsequence in array2[0] and the array1[x - 1] * and in the same way, we can easy to understand the measuring of the matrix[x, 1] x -> [1, n]: * The length of the longest common subsequence in array1[0] and the array2[x - 1] * so after fill, the matrix: * 1 2 3 4 5 6 7 * 2 0 1 1 1 1 1 1 * 5 0 0 0 0 0 0 0 * 6 0 0 0 0 0 0 0 * 7 0 0 0 0 0 0 0 * the base elements are ok, so we will use dynamic programming * if array1[x] == array2[y],we can know that it is form the "decreasing and conquer" * so we should make matrix[y - 1, x - 1] = matrix[y - 2, x - 2] + 1 * else array1[x] !
Data Structure String $Structure\rightarrow list$ linked String Arrayed String General Concepts of String $Null\ String(\emptyset)：Nothing\ in\ the\ string, the\ length\ is\ zero.$ $Blank(Space)string：Only\ includes\ one\ or\ more\ blanks(spaces)in\ the\ string.$ $Substring: sub-sequence\ of\ one\ string.$ ADT {
ADT String {Data Object：D＝{ ai | ai∈CharacterSet,i=1,2,...n, n≥0 } Data Relationship：R1＝{ < ai-1, ai > | ai-1, ai∈D,i=2,...,n } Operation： …… } ADT String
Operations {
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 StrAssign (&T, chars) //string assignment Initial：chars are character constant.
Data Structure Stack and Queue Stack Definition: Lists with the restriction that insertions and deletions can be performed in only one position, namely, the end of the list. Access the list from the top. First in, last out (FILO) lists Or last in, first out (LIFO) lists. Basic Concepts Top: the end of the list, namely, the operation end. Bottom: the head of the list Push: Insert an element into
