Description: This is a required course for Computer Science graduate students. It builds on the introduction to algorithmic design and analysis that students receive in 91. 404. Topics



Download 7.52 Kb.
Date02.05.2018
Size7.52 Kb.
#47318
Description:

This is a required course for Computer Science graduate students. It builds on the introduction to algorithmic design and analysis that students receive in 91.404.


Topics: Advanced Algorithm Design and Analysis, Data Structures

  • Advanced Analysis & Complexity Measures for Problems, Solutions, and Algorithms

  • Time

  • Space

  • Measures of Effectiveness to Support Challenging Problem Characteristics

  • Dynamic

  • Large-Scale

  • High-Dimension

  • Parallel Efficiency, Work

  • Output-Sensitivity

  • Amortized Analysis

  • NP-completeness

  • Partial Solutions

  • Algorithm & Solution Substructure

  • Models of Computation

  • Sequential

  • Comparison-Based

  • Parallel

  • Comparison-Based

  • PRAM: EREW, CREW, ERCW, CRCW

  • Advanced Algorithm Design/Paradigms

  • How to make an “Algorithm Sandwich” [when is your algorithm “good” enough?]

  • Greedy Algorithms

  • Dynamic Programming Algorithms

  • Approximation Algorithms & Schemes

  • On-Line Algorithms

  • Optimization Strategies

  • Advanced Search Strategies

  • Randomized Algorithms

  • Preprocessing & Sweep-Line Paradigm

  • Advanced Data Structures

  • Augmenting Data Structures

  • Interval Trees

  • [B-Trees]

  • Binomial Heaps

  • Fibonacci Heaps

  • Data Structures for Disjoint Sets

  • Advanced Algorithms for Specific Classes of Applications

  • Advanced Graph Algorithms

  • String Matching

  • Parallel Sorting Algorithms

  • Number-Theoretic Algorithms

  • Computational Geometry

  • Polynomials/FFT

  • Matrix Algorithms


Prerequisites: 91.500 and 91.404 or 91.583. Co-requisite 91.502. Standard graduate-level prerequisites for math background apply.

Homework: This is primarily a "paper-and-pencil" course whose homework and exams involve writing algorithms using pseudo-code", establishing their correctness and analyzing their efficiency. Although programming will not be required, programs will be provided whenever possible to illustrate and reinforce concepts. Students are also encouraged to implement their algorithms.
Download 7.52 Kb.

Share with your friends:




The database is protected by copyright ©ininet.org 2024
send message

    Main page