1. 1. Week 0


Algorithms, Part I
by Kevin Wayne, Robert Sedgewick
2016-06-17 FRI :start

Week 0

COurse Introduction

What is this course?

  • Intermediate-level survey course.


  • Programming and problem solving, with application

  • Algorithm: method for solving a problem.

  • Data structure: method to store information

topic data structures and algorithms
data types stack,queue,bag(?),union-find(并查集的数据结构),priority queue(优先队列)
sorting quicksort,mergesort*(归并排序)*,heapsort(堆排序)
searching BST,red-black BST,hash table
graphs BFS,DFS,Prim,Kruskal,Dijkstra
strings radix sorts,tries,KMP,regexps,data compression
advanced B-tree,suffix array*(后缀数组),maxflow(最大流增广路算法)*

1. Their impact is broad 影响 and far-reaching 深远


Web search, packet routing, distributed file sharing, …

Biology. 生物学 Human genome project人类基因组计划,protein folding蛋白质折叠,….

Computers. Circuit layout电路设计,file system,compilkers,….

Computer graphics. Movies,video games,virtual relity,…

Security. Cell phones, e-commerce,voting machines,…

Multimedia. MP3,JPG,DivX,HDTV,face recognition,…

Social networks. Recommendations,news feeds,advertisements,…

Physics. N-body simulation,particle collision simuluations,…

2. Old roots, new opportunities

  • Study of algorithms dates at least to Euclid. 欧几里得
  • Formalized by Church and Turing in 1930s.
  • Some important algorithms were discovered
    by undergraduates 大学生in a course like this!

3. To solve problems that could not otherwise be addressed
Ex. Network connectivity.[stay tuned]敬请期待

Network Connectivity

3. For intellectual stimulation

  • Francis Sullivan:

    “For me, great algorithms are the poetryn.诗 of computation. Just like
    verse诗篇, they can be terse精练, allusive, dense, and even mysterious.
    But once unlocked, they cast a brilliant new light on some
    aspect of computing. ”

  • Donald Knuth

    “An algorithm must be seen to be believed. ”

4. To become a proficient programmer.

Linus Torvalds (creator of Linux):

“ I will, in fact, claim that the difference between a bad programmer and a good one is whether he considers his code or his data structures
more important. Bad programmers worry about the code. Good programmers worry about data structures and their relationships. ”

  • Niklaus Wirth:

    “Algorithms + Data Structures = Programs. ”

4.They may unlock the secrets of life and of the universe

Computational models计算模型 are replacing math models in scientific inquiry科学探索
![Scientific inquiry]( “Scientific inquiry’)



It’s an intermediate level survey course on algorithms.We’re going to concentrate on programming and problem solving in the

Welcome.I’m Bob SDedgewick,professor of computer science at Princetion.

princeton: 普林斯顿


  1. 1. Week 0