Algorithms, Part I
by Kevin Wayne, Robert Sedgewick
2016-06-17 FRI :start
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|
|searching||BST,red-black BST,hash table|
|strings||radix sorts,tries,KMP,regexps,data compression|
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]敬请期待
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科学探索
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.