CSE385

Course CSE385
Title Analysis of Algorithms: Honors
Credits 4
Course Coordinator

Michael Bender

Description

Algorithmic design and analysis for Computer Science Honors students.  Mathematical analysis of a variety of computer algorithms including searching, sorting, matrix multiplication, fast Fourier transform, and graph algorithms. Time and space complexity. Upper-bound, lower-bound, and average-case analysis. Randomization.  Introduction to NP completeness. Some machine computation is required for the implementation and comparison of algorithms. 

Prerequisite CSE 260; AMS 210 or MAT 211; CSE Honors Program or Honors College or WISE
Course Outcomes
  • Ability to perform worst-case asymptotic algorithms analysis.
  • Ability to define and use classical combinatorial algorithms for problems such as sorting, shortest paths and minimum spanning trees.
  • Understanding of algorithmic techniques such as divide-and-conquer and dynamic programming. 
  • Understanding of computational intractability and NP completeness.

Textbook

Introduction to Algorithms, Third Edition
By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein 

Major Topics Covered in Course

 

 

Week 1.

introduction to course

several motivating problems

asymptotic notation

RAM and other computational models

Week  2.

divide and conquer

(merge sort, exponentiation, matrix multiplication, Strassens algorithm, median finding, master method)

Week  3.

divide and conquer

(median finding, closest pair problem)

Week  4.

dynamic programming

(edit distance, knapsack problem)    

Week  5.

dynamic programming

(space-efficient edit distance, shortest-path in dags and applications)

Week  6.

introduction to graphs

(directed and undirected graphs, depth first search and breadth first search, topological sort, shortest path algorithms)

Week  7.

minimum spanning trees

(Prims, Kruskalls, Boruvkas)

Week  8.

midterm plus midterm review

Week  9.

big data algorithms, external-memory algorithms, and cache-oblivious algorithms

(sorting, searching, matrix multiplication)

Week  10.

write-optimized data structures and its application in databases

Week  11.

randomized algorithms and data structures

(Karp-Rabin string matching, skip lists)

Week  12.

more data structures

(search trees and hashing)

Week  13.

NP completeness and reductions

Week  14.

NP completeness, reductions, and exam review

Laboratory Projects

N/A

Course Webpage