COURSE
DESCRIPTION:
This course is
aiming at providing students with an enjoyable introduction to the
field of algorithms. It is good that students have some programming
experience and some facility with proofs by mathematical induction.
The course will cover basic algorithm topics like Sorting and Order
Statistics, Data Structures, Dynamic Programming, Greedy Algorithms,
Amortized Analysis, Graph Algorithms, and some selected advanced
topics.
COURSE
OBJECTIVES:
Upon
completing this course, a student should be able to:
(1) Analyze
the asymptotic performance of algorithms.
(2) Demonstrate a familiarity with
major algorithms and data structures.
(3) Apply important algorithmic design
paradigms and methods of analysis.
(4) Synthesize efficient algorithms in
common engineering design situations.
COURSE
REQUIREMENTS:
A.
Reading:
Carefully read all
the assigned reading from the textbook.
B.
Exams:
The course will have
one midterm and one final.
COURSE TEXTBOOKS:
Required Textbooks:
Introduction
to Algorithms, Second Edition, by Cormen, Leiserson, Rivest, and
Stein.
Optional Textbooks:
Aho, Alfred V.,
John E. Hopcroft, and Jeffrey D. Ullman. The Design and Analysis of
Computer Algorithms. Reading, MA: Addison-Wesley, 1974. ISBN:
0201000296.
The classic text, but it lacks topics in network flows and linear programming, as well as more recent algorithms.
The classic text, but it lacks topics in network flows and linear programming, as well as more recent algorithms.
———. Data Structures and
Algorithms. Reading, MA: Addison-Wesley, 1983. ISBN:
0201000237.
Revised and more elementary version of the first six chapters of The Design and Analysis of Computer Algorithms.
Revised and more elementary version of the first six chapters of The Design and Analysis of Computer Algorithms.
Baase, Sara. Computer Algorithms:
Introduction to Design and Analysis. 2nd ed. Reading, MA:
Addison-Wesley, 1988. ISBN: 0201060353.
General reference, although the exposition is sometimes terse or sketchy.
Bentley, Jon Louis. Programming Pearls.
Reading, MA: Addison-Wesley, 1986. ISBN: 0201103311.
Applications of algorithm design techniques to software engineering.
Applications of algorithm design techniques to software engineering.
———. More Programming Pearls:
Confessions of a Coder. Reading, MA: Addison-Wesley, 1988. ISBN:
0201118890.
More applications of algorithm design techniques to software engineering.
———. Writing Efficient Programs.
Englewood Cliffs, NJ: Prentice-Hall, 1982. ISBN:
0139702512.
Performance hacking extraordinaire.
Performance hacking extraordinaire.
Brassard, Gilles, and Paul Bratley.
Algorithmics: Theory and Practice. Englewood Cliffs, NJ:
Prentice-Hall, 1988. ISBN: 0130232432.
Good examples and problems. Focus on methods rather than specific problems.
Good examples and problems. Focus on methods rather than specific problems.
Chung, Kai Lai. Elementary Probability
Theory with Stochastic Processes. New York, NY: Springer-Verlag,
1974. ISBN: 0387900969.
Intuitive introduction to probability.
Even, Shimon. Graph Algorithms.
Rockville, MD: Computer Science Press, 1979. ISBN: 0914894218.
Broad treatment of graph algorithms, including network flow and planarity.
Broad treatment of graph algorithms, including network flow and planarity.
Feller, William. An Introduction to
Probability Theory and Its Applications. 3rd ed. 2 vols. New
York, NY: John Wiley & Sons, 1968, 1971. ISBN: 0471257087. ISBN:
0471257095.
Excellent reference for probability theory.
Excellent reference for probability theory.
Class will be divided into 4-6 person teams. Each team will be provided a set of high-level requirements to be implemented, integrated, and tested. Each team’s requirements will be implemented using a selected set of the computer algorithms covered in the course. Teams may define their own project (subject to instructor approval) or select a project from a list provided by the instructor. By using pseudocode or even practical computer language like C, students should design and fulfill the computer algorithm. Then students learn how to use mathematics and computer to set up a mathematical model and solve the practical problems.
Sample Team
Project:
- FFT algorithm implementation like iterative method. To establish and describe a parallel FFT circuit using pseudocode.
- To construct a Huffman code and analyze its correctness.
COURSE SCHEDULE:
Week
1 Introduction of Analysis and Design of Algorithms Ch 1,2
-from required Insertion Sort, Mergesort
book
Week
2 Sorting,Medians and Other Statistics
Ch 6,7,9
Quicksort,heapsort
Week 3 Data
Structures I Ch
10
Stacks,
queues, linked lists,
Week 4
Data Structures II
Ch 11
Hash talbes, Universal Hashing, Perfect Hashing
Week 5 Trees
Ch 12,13
Binary Search, Red-Black Tree(Rotations, Insertions,
Deletions)
Week 6 Elementary
Graph Algorithms Ch 22,23
Representations of graphs, Breadth-first and
Depth-first search, Topological sort, Minimum
Spanning Trees
Week 7 Advanced
Graph Algorithms Ch 24-26
Shortest Paths, Maximum Flow
Week 8
Midterm
Week 9 Linear
Programming Ch 29
Week 10 Dynamic
Prgramming Ch 15
Assembly-line scheduling,Matrix-chain multiplication
Longest common subsequence
Week 11 Greedy
Algorithm Ch 16
Activity-selection scheduling,Matrix-chain
multipliction
Longest
common subequence
Week 12
Selected topics 1
Advanced Data Structures
Ch 18-20
B-Trees,Binomial Heaps,Fibonacci Heaps
Week 13 Selected
topics 1 Ch 32,30,28
String Matching, Polynimials and the FFT,Matrix
Operations
Week 14 Selected
topics 2 Ch 34,27
NP-Completeness, Sorting Networks
Week 15
Putting It All Together
Review
Week 16
Finals
No comments:
Post a Comment