Description:
This course will provide a rigorous introduction to the design and
analysis of algorithms. We will discuss classic problems (e.g., sorting,
traveling salesman problem), classic algorithm design strategies (e.g.,
divide-and-conquer, greedy approaches), and classic algorithms and data
structures (e.g., hash tables, Dijkstra's algorithm). We will also
analyze algorithm complexity throughout, and touch on issues of
tractibility such as "NP-Completeness". Texts:Required: Introduction to Algorithms (Second Edition) by Cormen, Leiserson, Rivest, and Stein, McGraw-Hill (2001).
This
book is similar to the first edition, so you could probably get by with
only the first edition. However, all homework problems assigned from
the book will be referenced from the second edition; it is your
responsibility to find a way to look them up. I strongly recommend that
you buy the text rather than borrow it; this is one of only two text
books that I still use on a regular basis. It is an indispensable
reference.
Lectures:
A tentative schedule of lecture topics is given below. The "CULTURE"
topics represent interesting but non-essential material from fields such
as computational geometry and computer graphics; they add some variety
to the schedule but also give us some slack if we get behind schedule.
If we cover a "culture" topic in class, you will be tested on it.
|
Number
|
Topic
|
Source
|
Text
|
|
1
|
--
| ||
|
2
|
3.1-3.2
| ||
|
3
|
4.1
| ||
|
4
|
4.3, 6.1-6.2
| ||
|
5
|
6, 7.1-7.3
| ||
|
6
|
7.4
| ||
|
7
|
5.1-5.3
| ||
|
8
|
5.4 last section
| ||
|
9
|
8.1-8.2
| ||
|
10
|
8.3-8.4
9.1-9.2 | ||
|
11
|
9.3
| ||
|
12
| |||
|
13
|
12.1-12.3
| ||
|
14
|
13.1-13.2
| ||
|
15
|
13.3-13.4
| ||
|
16
|
--
| ||
|
17
|
11.1-11.2
| ||
|
18
|
11.3-11.4
| ||
|
19
|
11.3-11.4
| ||
|
20
|
14.1-14.2
| ||
|
21
|
14.3
| ||
|
22
|
22.1-22.3
| ||
|
23
|
22.3
| ||
|
24
|
23.1
| ||
|
25
|
23.2
| ||
|
26
|
24.1-24.3
| ||
|
27
| |||
|
28
|
21.1-21.3, 23.2
| ||
|
29
|
17.1-17.2
| ||
|
30
|
17.3-17.4
| ||
|
31
|
15.1, 15.3
| ||
|
32
|
15.4
| ||
|
33
| |||
|
34
|
16.1-16.2
| ||
|
35
|
34.1-34.2
| ||
|
36
|
34.1-34.2
| ||
|
37
|
34.3-4
| ||
|
38
|
34.3-4
| ||
|
39
|
--
|
No comments:
Post a Comment
its cool