📄 http:^^www.cs.indiana.edu^classes^b403^index.html
字号:
Date: Wed, 20 Nov 1996 22:33:23 GMT
Server: Apache/1.0.3
Content-type: text/html
Content-length: 4367
Last-modified: Wed, 30 Oct 1996 04:24:28 GMT
<!doctype htmlplus public "-//Internet/RFC xxxx//EN"><htmlplus><head><title>B403 (Spring `97) home page</title></head><body><center><h2>B403 (Spring `97)<br>Introduction to Algorithm Design and Analysis</h2><p>[ <a href="#info">General Information</a>| <a href="#outline">Course Outline</a>| <a href="#lectures">Lectures</a>| <a href="#assignments">Assignments</a><!--| <a href="#tools">Tools</a>-->]</center><hr><a name="info"><h3>General Information</h3></a><p><strong>Course description:</strong> This course is for students interested in designing computeralgorithms and analyzing their efficiencies. The study of algorithmsis at the very heart of computer science. The course will cover basicalgorithm design techniques, including divide and conquer, recurrence,dynamic programming, greedy algorithms, and reduction to knownproblems, as well as basic algorithm analysis techniques, includingworst case analysis, average case analysis, and probabilisticanalysis. We will study various searching and sorting algorithms aswell as a number of graph algorithms.<p><strong>Prerequisites:</strong> C221 and C343 (or their honors equivalents) and Mathematics M216,or instructor's permission | <strong>Credits:</strong> 3<p><strong>Instructor:</strong> <ahref="http://www.cs.indiana.edu/hyplan/liu.html">Y. Annie Liu</a> |<strong>Email:</strong> <ahref=mailto:liu@cs.indiana.edu>liu@cs.indiana.edu</a> |<strong>Office:</strong> 201E Lindley Hall<p><strong>Hours:</strong> MW 2:30PM-3:45PM, in Lindley Hall 019 |<strong>Office Hours:</strong>MW 3:45PM-4:45PM<p><strong>Textbook:</strong> <em>Introduction to Algorithms</em> byThomas Cormen, Charles Leiserson, and Ronald Rivest. MIT andMcGraw-Hill, 1990 (Fifteenth printing, 1995)<hr><strong>A clarification:</strong> This course does not haveprogramming projects. However, if you like programming, you shouldknow that algorithms are written as pseudo code and, if you are goodat them, you can turn them into real code easily. These algorithmsare used in many applications, and there are programs written for themalready. You may play with those programs if you like, but you willhave to know the algorithms to understand how the programs work.<hr><a name="outline"><h3>Tentative Course Outline</h3></a><p><li> We will first introduce analysis of algorithms. This includesasymptotic notation, summations and recurrences, counting andprobability, lower bounds. They will not be introduced in abstract,instead we will discuss sorting and related algorithms (insertionsort, mergesort, quicksort, heapsort, median and order statistics) aswell as Strassen's matrix multiplication algorithms (Parts I-II:chapters 2-4, 6, 7-10, 31.2)<p><li> We will then discuss data structures. They include hashtables, binary search trees, red-black trees, skip lists, andaugmenting data structures. The last piece will start the study ofalgorithm design, although some design techniques (recurrence,divide-and-conquer) will have been covered while introducing analysistechniques. (Part III: chapters 12-15)<p><li> We will then study advanced algorithm design techniques(dynamic programming, greedy algorithms) and analysis techniques(amortized analysis). These techniques will not be introduced inabstract, instead we will discuss problems such as longest commonsubsequence, activity selection, and minimum spanning tree. This lastexample will start study of graph algorithms. (Part IV: chapters16-18, 24)<p><li> We will then discuss graph algorithms. This include basicalgorithms like depth-first search, breadth-first search, topologicalsort, and strongly connected components, as well as more advancedalgorithms for single-source/all-pairs shortest paths problems andnetwork flow problems. (Part VI: chapters 23, 25-27)<p><li>We will at the end introduce a few selected topics. Possible choicesare parallel algorithms, incremental/dynamic algorithms, polynomialsand FFT, string matching, and computational geometry. (Part VII:chapters 28?, 29?, 32?, 34?, 35?)<hr><a name="lectures"><h3>Lectures</h3></a><hr><a name="assignments"><h3>Assignments</h3></a><hr><!--<a name="tools"><h3>Tools</h3></a><hr>--><a href=mailto:liu@cs.indiana.edu><kbd>liu@cs.indiana.edu</kbd></a>Last updated October 29, 1996</body></htmlplus>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -