Design & Analysis of Algorithms - CS 4/56101

MW 12:30 pm - 1:45 pm
MSB 115

 

 

Presentations

 

Chapters

Topics

Reading

 Instead of Introduction

    By Jeff Edmonds

 

Chapter 1: Algorithm Analysis

    Analysis of Algorithms

   Sections: 1.1,1.2,1.3,1.4

Chapter 2: Basic Data Structures

·  Elementary Data Structures 

·  Vectors 

·  Stacks 

·  Queues 

·  Sequences 

·  Trees 

·  Heaps 

·  Priority Queues 

·  Hash Tables 

·  Dictionaries 

·  Sections: 2.1,2.2,2.3

·  Sections: 2.2.1

·  Sections: 1.5,2.1.1

·  Sections: 2.1.2

·  Sections: 2.2.2,2.2.3

·  Sections: 2.3.1 - 2.3.4

·  Sections: 2.4.1,2.4.3

·  Sections: 2.4.1 - 2.4.4

·  Sections: 2.5.1 - 2.5.6

·  Sections: 3.1.1 - 3.1.6

Chapter 3: Search Trees and Skip Lists

·  Binary Search Trees 

·  Red-Black Trees

·  Sections: 3.1.1 - 3.1.6

·  Sections: 3.3.3 

Chapter 4: Sorting, Sets, and Selection

·  Merge Sort

·  Quick Sort 

·  Sorting Lower Bound 

·  Sets 

·  Radix Sort 

·  Selection 

·  Sections: 4.1.1 

·  Sections: 4.3.1, 4.6 

·  Sections: 4.4

·  Sections: 4.2.1 

·  Sections: 4.5.1, 4.5.2 

·  Sections: 4.7, 4.7.1 - 4.7.3

Chapter 5: Fundamental Techniques

·  Greedy Method 

·  Divide-and-Conquer 

·  Dynamic Programming 

·  Sections: 5.1,5.1.1, 5.1.2 

·  Sections: 5.2, 5.2.1 - 5.2.3

·  Sections: 5.3, 5.3.1 - 5.3.3 

Chapter 6: Graphs

·  Graphs 

·  Depth-First Search 

·  Breadth-First Search 

·  Biconnectivity 

·  Directed Graphs 

·  Sections: 6.1- 6.2

·  Sections: 6.3.1

·  Sections: 6.3.3

·  Sections: 6.3.2

·  Sections: 6.4.1, 6.4.2, 6.4.4

Chapter 7: Weighted Graphs

·  Shortest Paths 

·  Minimum Spanning Tree

·   Sections: 7.1, 7.1.1-7.1.3, 7.2, 7.2.1

·   Sections: 7.3, 7.3.1-7.3.3

Chapter 8: Network Flow and Matching

·  Network Flow 

·   Sections: 8.1.1, 8.1.2, 8.2.1-8.2.3

Chapter 9: Text Processing

·  Pattern Matching 

·   Sections: 9.1.1 -  9.1.4

Demos

·  Minimum Spanning Tree 

·  Shortest Path by Dijkstra's Algorithm 

·  A Stable Marriage Applet

·  An Applet of SkipList

·  An Applet of Max Flow

·  An Applet of Line Sweeping Algorithm

·  An Applet of Graham's scan (Convex Hull Algorithm) 

Textbook:  Algorithm Design: Foundations, Analysis,  and Internet Examples, Wiley, 2002, 
ISBN 0-471-38365-1

 

 

by 
Michael T. Goodrich,
Univ. of California, Irvine 
and 
Roberto Tamassia, 
Brown Univ. 

Book's web site

HOMEWORKS 

    • Homework #1: distributed on  2/2/2009, due 2/9/2009 results
    • Homework #2: distributed on  2/9/2009, due 2/16/2009 results
    • Homework #3: distributed on  2/16/2009, due 3/2/2009 results
    • Homework #4: distributed on  2/25/2009, due 3/9/2009 results
    • Homework #5: distributed on  4/6/2009, due 4/13/2009 results
    • Homework #6: distributed on  4/13/2009, due 4/20/2009 results
    • Homework #7: distributed on  4/20/2009, due 4/29/2009 results

 

                 Extra credit problem: distributed on 4/15/2009, due 4/27/2009. results

EXAMS

    • Wednesday, March 18, 2009, 12:30 pm - 1:45 pm (All material covered before Chapter 5)  Info   Overview    Results 

      MidTerm Review is on Monday, March 16, 2009.

    • Wednesday, May 13, 2009, 10:15 am - 12:30 pm Info Overview 

                         Final Exam Review is on Wednesday, May 6, 2009.

FINAL GRADES

 

 

F. F. Dragan
dragan at cs dot kent dot edu
Spring 2009