Contents
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.

Intermediate-level:中级别的

• 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

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

Internet.

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,…

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]敬请期待

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](http://7xsic8.com1.z0.glb.clouddn.com/Scientificinquiry.jpg “Scientific inquiry’)

formula:公式

/*

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: 普林斯顿

*/

Contents
1. 1. Week 0