CS 301
Algorithms
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 : | Introduction
to Algorithms Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein The MIT Press |
|
Instructor : | Hüsnü Yenigün |
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