CS 301
Algorithms

WB01153_.GIF (2188 bytes)

Description : This course will cover algorithms for a variety of problems, as well as general algorithm design and analysis techniques such as divide-and-conquer, dynamic programming, and greedy algorithms. Specific topics include algorithm analysis, recurrences and asymptotic analysis; searching, sorting; algorithms for fundamental graph problems, such as depth-first search, connected components, topological sort, shortest paths.
Credits : 3
Pre-requisites : CS 202 Minimum Grade: D and MATH 204 Minimum Grade: D
Textbook : book-cover.jpg (8119 bytes) Introduction to Algorithms
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
The MIT Press
Instructor : Hüsnü Yenigün

WB01153_.GIF (2188 bytes)

Tentative outline :

Chapters covered from the textbook :

Chapter 2 - Getting Started
2.1 Insertion Sort
2.2 Analyzing Algorithms
2.3 Designing Algorithms
(also 28.2 - Strassen's Matrix Multiplication)

Chapter 3 - Growth of Functions
3.1 Asymptotic Notations

Chapter 4 - Recurrances
4.1 The Substitution Method
4.2 The Recursion-Tree Method
4.3 The Master Method
4.4 The Proof of the Master Theorem

Chapter 7 - Quicksort
7.1 Description of Quicksort
7.2 Performance of Quicksort
7.3 A Randomized Version of Quicksort
(note: We didn't study this in class but we
learned the basic idea in a similar
analysis on randomized selection algorithm)

Chapter 8 - Sorting in Linear Time
8.1 Lower Bounds for Sorting
8.2 Counting Sort
8.3 Radix Sort

Chapter 9 - Medians and Order Statistics
9.1 Minimum and Maximum
9.2 Selection in Expected Linear Time
9.3 Selection in Worst-case Linear Time

Chapter 12 - Binary Search Trees
12.1 What is a Binary Search Tree?
12.2 Querying a Binary Search Tree
12.3 Insertion and Deletion

Chapter 13 - Red-Black Trees
13.1 Properties of Red-Black Trees
13.2 Rotations
13.3 Insertion
13.4 Deletion

Chapter 14 - Augmenting Data Structures
14.1 Dynamic Order Statistics
14.2 How to Augment a Data Structure
14.3 Interval Trees

Chapter 15 - Dynamic Programming
15.2 Matrix-chain Multiplication
15.3 Elements of Dynamic Programming
15.4 Longest Common Subsequence

Chapter 16 - Greedy Algorithms
16.1 An Activity Selection Problem
16.2 Elements of the Greedy Strategy
16.3 Huffman Codes

Chapter 17 - Amortized Analysis
17.1 Aggregate Analysis
17.2 The Accounting Method
17.3 The Potential Method

Chapter 18 - B-Trees
18.1 Definition of B-Trees
18.2 Basic Operations on B-Trees
18.3 Deleting a Key from a B-Tree

Chapter 23 - Minimum Spanning Trees
23.1 Growing a Minimum Spanning Tree
23.2 The Algorithms of Kruskal and Prim

Chapter 24 - Single Source Shortest Paths
24.1 The Bellman-Ford Algortihm
24.2 Single Source Shortest Paths in Directed Acyclic Graphs
24.3 Dijkstra's Algorithm
24.4 Difference Constraints and Shortest Paths

Chapter 25 - All Pairs Shortest Paths
25.1 Shortest Paths and Matrix Multiplication
25.2 The Floyd-Warshall Algortihm

Chapter 26 - Maximum Flow
26.1 Flow Networks
26.2 The Ford-Fulkerson Method
26.3 Maximum Bipartite Matching

Chapter 27 - Sorting Networks
27.1 Comparison Networks
27.2 The Zero-one Principle
27.3 A Bitonic Sorting Network
27.4 A Merging Network
27.5 A Sorting Network

Chapter 33 - Computational Geometry
33.1 Line-segment Properties
33.2 Determining whether any pair of segments intersects
33.3 Finding the convex hull
33.4 Finding the closest pair of points

Chapter 34 - NP-Completeness
34.1 Polynomial time
34.2 Polynomial time verification
34.3 NP-Completeness and reducibility
34.4 NP-Completeness proofs
34.5 NP-Complete problems