CSE423/823 Spring 2003
Design and Analysis of Algorithms
Archived Class
Charles Cusack
Computer Science and Engineering
University of Nebraska--Lincoln



CSCI 255
MATH 132

previous     next     today     future     all    

Schedule for weeks 1 through 16

Wk Day Date TopicResourcesEvents

1MonJan 13Introduction to the CourseCourse Website

WedJan 15Analysis of Quicksort
  • CLRS Chapter 7.4
  • Quicksort Analysis notes

  • FriJan 17Lower bounds for Sorting
  • CLRS Chapter 8.1
  • Comparison Sort Lower Bound Lecture Notes
  • Pretest

    2MonJan 20Martin Luther King DayNo Class

    WedJan 22Finding
  • Minimum
  • Maximum
  • ith item
  • CLRS Chapter 9.1-9.2
  • Medians and Order Statistics Lecture Notes

  • FriJan 24ith order statistic: A better algorithmCLRS Chapter 9.3

    3MonJan 27
  • Finish Order Statistics
  • Start Dynamic Programming Dynamic Programming
  • The Elements of Dynamic Programming
  • Example: MCM

  • WedJan 29Dynamic Programming
  • Example: MCM
  • Example: 0-1 Knapsack
  • CLRS Chapter 15.1-15.3
  • An Introduction to Dynamic Programming Lecture Notes

  • FriJan 31More Dynamic Programming
  • LCS

  • 4MonFeb 03LCS
  • CLRS Chapter 15.4-15.5
  • Dynamic Programming Lecture Notes
  • HW1 Due

    WedFeb 05Optimal Polygon Triangulation

    FriFeb 07Greedy Algorithms:
    Activity Selection Problem
  • Introduction to Greedy Algorithms (review)
  • Minimum Spanning Trees (review)
  • Greedy Algorithms
  • CLRS Sections 16.1-16.3

  • 5MonFeb 10Review of Homework 1

    WedFeb 12Minimum Spanning Trees Greedy Algorithms Lecture Notes

    FriFeb 14Huffman Encoding Huffman Encoding Info and Applet

    6MonFeb 17Optimal Binary Search Trees

    WedFeb 19Amortized Analysis
  • CLRS Chapter 17
  • Amortized Analysis Lecture Notes

  • FriFeb 21Amortized AnalysisHW 2 due

    7MonFeb 24Amortized Analysis

    WedFeb 26Network Flow
  • CLRS Sections 26.1-26.3
  • Maximum Flow Lecture Notes

  • FriFeb 28Network Flow Problems

    8MonMar 03Residual Networks and Augmenting Paths

    WedMar 05Max-flow min-cut theorem

    FriMar 07Ford Fulkerson Method Ford Fulkerson Algorithm Applet

    9MonMar 10P, NP, NP-Complete
  • P, NP, and NP-Complete (review)
  • HW 3 due

    WedMar 12Review for Midterm

    FriMar 14
  • Searching, Sorting, and Bounds
  • Greedy Algorithms
  • Dynamic Programming
  • Amortized Analysis
  • Network Flow
  • Pencil, PaperMidterm Exam

    Spring Break Week

    10MonMar 24Introduction to P, NP, NPC
  • CLRS Section 34.1
  • NP-Completeness Lecture Notes

  • WedMar 26Verification and NPCLRS section 34.2

    FriMar 28NPC and ReductionsCLRS 34.3

    11MonMar 31NPC ProofsCLRS 34.4

    WedApr 02NPC Proofs34.4-34.5

    FriApr 04NPC Proofs

    12MonApr 07Approximation AlgorithmsCLRS Chapter 35

    WedApr 09Approximation Algorithm: Travelling Salesman Problem

    FriApr 11CSE DayNo Class
    HW4 Due

    13MonApr 14Approximation Algorithm: Set Covering

    WedApr 16Approximation Algorithm: Subset-Sum

    FriApr 18

    14MonApr 21

    WedApr 23

    FriApr 25

    15MonApr 28HW 5 due

    WedApr 30

    FriMay 02

    ExFriMay 09Final Exam 7:30am