http://algs4.cs.princeton.edu/
What is this course?
1.Intermediate-level survey course.
2.Programming and problem solving, with applications
3.Key points
3.1 Algorithm:method for solving a problem.
3.2 Data structure:method to store information associated in problem.
| topic | data structures and algorithms |
|---|---|
| data types | stack, queue, bag, union-find, priority queue |
| sorting | quicksort, mergesort, heapsort, radix sorts |
| 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 |
BST:Binary Search Tress
Why study algorithms?
Algorithm's impact is broad and far-reaching
| domain | application |
|---|---|
| Internet | Web search, packet routing, distributed file sharing, ... |
| Biology | Human genome project, protein folding, ... |
| Computers | Circuit layout, file system, compilers, ... |
| Computer graphics | Movies, video games, virtual reality, ... |
| Security | Cell phones, e-commerce, voting machines, ... |
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
To solve problems that could not otherwise be addressed
intellectual stimulation
"An algorithm must be seen to be believed, and the best way to learn what an algorithm is all about is to try it. " — Donald Knuth
To become a proficient programmer
"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."
— Linus Torvalds (creator of Linux)
Unlock the secrets of life and of the universe
Computational models are replacing math models in scientific inquiry.
So, more and more and more now a days people are developing computational models, where they attempt to simulate what might be happening in nature in order to try to better understand it.
Prerequisites
- Programming: loops, arrays, functions, objects, recursion.
- Java: we use as expository language.
- Mathematics: high-school algebra.
Review of prerequisite material.
- Quick: Sections 1.1 and 1.2 of Algorithms, 4th edition.
- In-depth: An Introduction to programming in Java: an interdisciplinary
approach by Sedgewick and Wayne.
Programming environment.
- Use your own, e.g., Eclipse.IDEA.
- Download ours (see instructions on web).
