上海交通大学精品课程《数据结构》俞勇

Lecture 01 Course Overview

Lecture 02 Bits, Bytes, and Integer

Lecture 03 Bits, Bytes, and Integers cont

Lecture 04 Floating Point

Lecture 05 Machine Level Programming I Basics

Lecture 06 Machine Level Programming II Control

Lecture 07 Machine Level Programming III Procedures

Lecture 08 Machine Level Programming IV Data

Lecture 09 Machine Level Programming V Advanced Topics

Lecture 10 Program Optimization

Lecture 11 The Memory Hierarchy

Lecture 12 Cache Memories

Lecture 13 Linking

Lecture 14 Exceptional Control Flow Exceptions and Processes

Lecture 15 Exceptional Control Flow Signals and Nonlocal Jumps

Lecture 16 System Level I_O

Lecture 17 Virtual Memory Concepts

Lecture 18 Virtual Memory Systems

Lecture 19 Dynamic Memory Allocation Basic Concepts

Lecture 20 Dynamic Memory Allocation Advanced Concepts

Lecture 21 Network Programming Part 1

Lecture 22 Network Programming Part II

Lecture 23 Concurrent Programming

Lecture 24 Synchronization Basics

Lecture 25 Synchronization Advanced

Lecture 26 Thread Level Parallelism

[第1集] 课程简介及算法分析

[第2集] 渐近符号、递归及解法

[第3集] 分治法（1）

[第4集] 快排及随机化算法

[第5集] 线性时间排序

[第6集] 顺序统计、中值

[第7集] 哈希表

[第8集] 全域哈希和完全哈希

[第9集] 二叉搜索树

[第10集] 平衡搜索树

[第11集] 扩充的数据结构、动态有序统计和区间树

[第12集] 跳跃表

[第13集] 平摊分析，表的扩增，势能方法

[第14集] 竞争性分析，自组织表

[第15集] 动态规划，最长公共子序列

[第16集] 贪婪算法，最小生成树

[第17集] 最短路径算法：Dijkstra算法，广度优先搜索

[第18集] 最短路径算法：Bellman和差分约束系统

[第19集] 最短路径算法：点的最短路径

[第20集] 高级课题 并行算法（一）

[第21集] 高级课题 并行算法（二）

Part1 1-03_course-introduction

Part1 2-03_dynamic-connectivity

Part1 2-04_quick-find

Part1 2-05_quick-union

Part1 2-06_quick-union-improvements

Part1 2-07_union-find-applications

Part1 3-02_analysis-of-algorithms-introduction

Part1 3-03_observations

Part1 3-04_mathematical-models

Part1 3-05_order-of-growth-classifications

Part1 3-06_theory-of-algorithms

Part1 3-07_memory

Part1 4-03_stacks

Part1 4-04_resizing-arrays

Part1 4-05_queues

Part1 4-06_generics

Part1 4-07_iterators

Part1 4-08_stack-and-queue-applications-optional

Part1 5-02_sorting-introduction

Part1 5-03_selection-sort

Part1 5-04_insertion-sort

Part1 5-05_shellsort

Part1 5-06_shuffling

Part1 5-07_convex-hull

Part1 6-03_mergesort

Part1 6-04_bottom-up-mergesort

Part1 6-05_sorting-complexity

Part1 6-06_comparators

Part1 6-07_stability

Part1 7-02_quicksort

Part1 7-03_selection

Part1 7-04_duplicate-keys

Part1 7-05_system-sorts

Part1 8-03_apis-and-elementary-implementations

Part1 8-04_binary-heaps

Part1 8-05_heapsort

Part1 8-06_event-driven-simulation-optional

Part1 9-02_symbol-table-api

Part1 9-03_elementary-implementations

Part1 9-04_ordered-operations

Part1 9-05_binary-search-trees

Part1 9-06_ordered-operations-in-bsts

Part1 9-07_deletion-in-bsts

Part1 10-03_2-3-search-trees

Part1 10-04_red-black-bsts

Part1 10-05_b-trees-optional

Part1 11-02_1d-range-search

Part1 11-03_line-segment-intersection

Part1 11-04_kd-trees

Part1 11-05_interval-search-trees

Part1 11-06_rectangle-intersection

Part1 12-03_hash-tables

Part1 12-04_separate-chaining

Part1 12-05_linear-probing

Part1 12-06_hash-table-context

Part1 13-02_symbol-table-applications-sets-optional

Part1 13-03_symbol-table-applications-dictionary-clients-optional

Part1 13-04_symbol-table-applications-indexing-clients-optional

Part1 13-05_symbol-table-applications-sparse-vectors-optional

Part2 1-03_course-introduction

Part2 2-03_introduction-to-graphs

Part2 2-04_graph-api

Part2 2-05_depth-first-search

Part2 2-06_breadth-first-search

Part2 2-07_connected-components

Part2 2-08_graph-challenges

Part2 3-02_introduction-to-digraphs

Part2 3-03_digraph-api

Part2 3-04_digraph-search

Part2 3-05_topological-sort

Part2 3-06_strong-components

Part2 4-03_introduction-to-msts

Part2 4-04_greedy-algorithm

Part2 4-05_edge-weighted-graph-api

Part2 4-06_kruskals-algorithm

Part2 4-07_prims-algorithm

Part2 4-08_mst-context

Part2 5-02_shortest-paths-apis

Part2 5-03_shortest-path-properties

Part2 5-04_dijkstras-algorithm

Part2 5-05_edge-weighted-dags

Part2 5-06_negative-weights

Part2 6-03_introduction-to-maxflow

Part2 6-04_ford-fulkerson-algorithm

Part2 6-05_maxflow-mincut-theorem

Part2 6-06_running-time-analysis

Part2 6-07_java-implementation

Part2 6-08_maxflow-applications

Part2 7-02_strings-in-java

Part2 7-03_key-indexed-counting

Part2 7-04_lsd-radix-sort

Part2 7-05_msd-radix-sort

Part2 7-06_3-way-radix-quicksort

Part2 7-07_suffix-arrays

Part2 8-03_r-way-tries

Part2 8-04_ternary-search-tries

Part2 8-05_character-based-operations

Part2 9-02_introduction-to-substring-search

Part2 9-03_brute-force-substring-search

Part2 9-04_knuth-morris-pratt

Part2 9-05_boyer-moore

Part2 9-06_rabin-karp

Part2 10-03_regular-expressions

Part2 10-04_res-and-nfas

Part2 10-05_nfa-simulation

Part2 10-06_nfa-construction

Part2 10-07_regular-expression-applications

Part2 11-02_introduction-to-data-compression

Part2 11-03_run-length-coding

Part2 11-04_huffman-compression

Part2 11-05_lzw-compression

Part2 12-03_introduction-to-reductions

Part2 12-04_designing-algorithms

Part2 12-05_establishing-lower-bounds

Part2 12-06_classifying-problems

Part2 13-02_brewers-problem

Part2 13-03_simplex-algorithm

Part2 13-04_simplex-implementations

Part2 13-05_linear-programming-reductions

Part2 14-02_introduction-to-intractability

Part2 14-03_search-problems

Part2 14-04_p-vs-np

Part2 14-05_classifying-problems

Part2 14-06_np-completeness

Part2 14-07_coping-with-intractability

一.2

一.3

一.4

二.1

二.2

二.3

二.4

三.1

三.2

四.1

四.2

五.1

五.2

五.3

五.4

五.5

五.6

五.7

六.1

六.2

六.3

六.4

七.1

七.2

八.1

八.2

八.3

八.4

八.5

八.6

八.7

八.8

九.1

九.2

十.1

十.2

十.3

十一.1

十一.2

十二.1

十二.2

十二.3

十三.1

十三.2

十三.3

十四.1

十四.2

十五.1

十五.2

十五.3

十五.4

十五.5

十五.6

十五.7

十六.1

十六.2

十六.3