Design & Analysis of Algorithms - CS 4/56101

MW 12:30 pm - 01:45 pm

 

MSB 104

 

 

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

o   Minimum Spanning Tree 

o   Shortest Path by Dijkstra's Algorithm 

o   A Stable Marriage Applet

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 1/24/2018, due 2/05/2018
    • Homework #2: distributed on 2/05/2018, due 2/12/2018
    • Homework #3: distributed on 2/12/2018, due 2/26/2018
    • Homework #4: distributed on 2/26/2018, due 3/05/2018
    • Homework #5: distributed on 3/14/2018, due 4/02/2018
    • Homework #6: distributed on 4/04/2018, due 4/16/2018
    • Homework #7: distributed on 4/16/2018, due 4/25/2018

 


EXAMS


o    Wednesday, March 14, 2018, 12:30 pm - 1:45 pm (All material covered before Chapter 5) (Info, Overview)

Mid-Term Review is on Monday, March 12, 2018.

 

o    Tuesday, May 8, 2018, 10:15 - 12:30 p.m (Info, Overview)

Final Exam Review is on Wednesday, May 02, 2018.

 

 

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