Bookmark and Share







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.

Click Below to Download the files :-

Lectures:
A tentative schedule of lecture topics is given below.
NumberDateTopicSourceText
11/16Introduction, administration, time and space complexity--
21/18Basics: asymptotic notationPPT3.1-3.2
31/21Basics: recurrences (mergesort)PPT4.1
41/23Basics: recurrences continued, master theoremPPT4.3, 6.1-6.2
51/25Sorting: intro to heapsortPPT6, 7.1-7.3
61/28Sorting: heapsort, priority queuesPPT7.4
71/30Sorting: quicksortPPT5.1-5.3
82/1Sorting: quicksort average case analysisPPT5.4 last section
92/4Sorting: linear time sorting algorithmsPPT8.1-8.2
102/6Sorting: linear time algorithms continued;
Order statistics: selection in expected linear time
PPT8.3-8.4
9.1-9.2
112/8Order statistics: selection in worst-case linear timePPT9.3
122/11Review for examPPT
EXAM2/13EXAM 1: Basics, Sorting, Order Statistics
--
132/15Structures: binary search treesPPT12.1-12.3
142/18Structures: red-black treesPPT13.1-13.2
152/20Structures: red-black trees (insertion)PPT13.3-13.4
162/22Structures: skip listsPPT--
172/25Structures: skip lists, hash tables PPT11.1-11.2
182/27Structures: hash tables (hash functions)PPT11.3-11.4
193/1Structures: hash tables (universal hashing)PPT11.3-11.4
203/4Augmenting structures: dynamic order statisticsPPT14.1-14.2
213/6Augmenting structures: interval treesPPT14.3
223/8Graph algorithms: the basicsPPT22.1-22.3
----SPRING BREAK
--
233/18Graph algorithms: BFSPPT22.3
243/20Graph algorithms: DFSPPT23.1
EXAM3/22EXAM 2: Data structures
--
--3/25Go over exam
--
253/27Minimum spanning treesPPT23.2
263/29Shortest paths: Bellman-FordPPT24.1-24.3
274/1Shortest paths: DAG, Dijkstra's algorithmPPT
284/3Finish Dijkstra's. Kruskals algorithm; disjoint setsPPT21.1-21.3, 23.2
294/5Disjoint sets; amortized analysisPPT17.1-17.2
304/8Amortized analysis continuedPPT17.3-17.4
314/10Dynamic programming PPT15.1, 15.3
324/12Dynamic programming (longest common subsequence)PPT15.4
334/15Dynamic programming (knapsack problem)PPT
344/17Greedy algorithms PPT16.1-16.2
354/19NP-CompletenessPPT34.1-34.2
364/22NP-Completeness continuedPPT34.1-34.2
374/24NP-Completeness: reductionsPPT34.3-4
384/26NP-Completeness: reductionsPPT34.3-4
394/29Review for finalPPT--
EXAM5/9FINAL EXAMINATION: 2 PM
 

Our Followers

Speak to us !

Creative Commons License [Valid RSS] [Valid Atom 1.0] DMCA.com ScanVerify.com Trust Seal