Algorithms

Office: Room 7301.07

Classroom: TBA

Time: 24PM Tuesdays
Course Description
Algorithm analysis evaluates time and memory resource requirements of a proposed algorithm as a function of input length. Algorithm design studies techniques for constructing algorithms with minimal resource requirements. This course covers mainly the design and analysis for a number of important and common algorithms, including divide and conquer, randomized algorithms, sorting, hash tables, binary search trees, dynamic programming, greedy algorithms, data structures for disjoint sets, graph algorithms, spanning trees and shortest paths. In addition, handson projects will be assigned to the students to implement fundamental and advanced computer algorithms in real applications.
Topic List

Growth of Functions

DivideandConquer

Probabilistic Analysis and Randomized Algorithms

Heapsort

Sorting in Linear Time

Hash Tables

Binary Search Trees

Dynamic Programming

Greedy Algorithms

Data Structures for Disjoint Sets

Elementary Graph Algorithms

Minimum Spanning Trees

Single Source Shortest Paths
Learning Goals
The student should be able to:

Understand and program the most efficient algorithms for sorting and prove their optimality

Understand and program divide and conquer algorithms using tree search methods

Understand the principles of greedy algorithms

Know the definitions of graphs and analyze and program graph traversal algorithms and calculate minimum spanning trees
Assessment

There will be a homework assignment on each of the thirteen topics listed in the Topic List. These will be oriented toward testing the understanding and ability to program of the various algorithms as stated in the Learning Goals. These assignments will determine 65% of the final grade.

There will be a final exam consisting of problems the solution of which should demonstrate the student's understanding of various algorithms from the Topic List. This will be responsible for 35% of the final grade.
Text Book
Introduction to Algorithm (Latest Edition), Cormen, Leiserson, Rivest, and Stein, MIT press