CS532 ANALYSIS AND DESIGN OF ALGORITHMS

Winter 2009
Tuesday/Thursday, 6:10-7:40 p.m, Wilson Clark Center - Room 403


Instructor

Sava Krstic

971/214-1708
sava dot krstic at intel dot com


Textbook

Thomas Cormen, Charles Leiserson, Ronald Rivest and Cliff Stein: Introduction to Algorithms, second edition, MIT Press and McGraw-Hill, 2003.

Tentative Schedule

  • Week 1: Preliminaries (Ch. 1-4)
    • What is an algorithm?
    • Measuring performance
    • Big-Oh and similar notations

  • Week 2: Data Structures (Ch. 10,6,12)
    • Basic structures (arrays, lists, trees, dictionaries, sets)
    • Binary search trees
    • Heaps

  • Weeks 3,4: Sorting and Searching (Ch. 6-8,13,18)
    • Insertion sort, heapsort, quicksort, mergesort, lower bounds for sorting
    • AVL-trees, red-black trees, B-trees, splay trees

  • Week 5: Hashing (Ch. 11) and Midterm

  • Week 6: Design and Analysis Techniques (Ch. 15-17)
    • Dynamic programming
    • Greedy algorithms
    • Amortized analysis

  • Weeks 7,8: Graph Algorithms
    • Traversals, topological sort, strongly connected components
    • Minimum spanning trees
    • Shortest paths

  • Week 9: Computational Geometry (Chapter 33)
    • Line-segment intersection
    • Convex hulls

  • Week 10: NP-Completeness (Ch. 34)


Homework

There will be seven assignments. They will be given on Tuesdays and handed in on Tuesday the following week. For problems involving programming, you can use any programming language.


Tests

Two in-class 15 minute quizzes will be assigned during weeks 3 and 8. The midterm will probably be on February 5, and the final on March 17. Quizzes will be ``closed book'', and exams will be ``open book and notes''.


Grading Policy

Homework will account for 30% of the grade, quizzes for 15%, midterm for 25%, and the final for 30%.


Mailing List

To be announced.


Lecture Notes


Assignments

General inquiries:
csedept@cse.ogi.edu
503.748.1151
503.748.1553 FAX

Department of Computer
Science and Engineering
Oregon Graduate Institute
20000 NW Walker Road
Beaverton, OR 97006-8921


Education | Admission | Research | Student Life | People | News šÔ Events | Additional Resources
Home | OGI