COM 1390 Algorithms

Course Description and Catalog Information
Course Information (links to past and current course materials)
Course Format
Course Coordinator
Textbooks and References
Course Goals
Prerequisites by Topic
Major Topics Covered in Course
Laboratory Projects

Course Description

Introduces the basic principles and techniques for the discovery, design, analysis, and implementation of efficient algorithms.  Sample algorithms will be drawn from sorting and searching, graph algorithms, string matching algorithms, greedy algorithms, and dynamic programming.  Analysis will use both theoretical and experimental techniques.  The course will conclude with a discussion of "hard problems" for which no efficient algorithms are known and will introduce the concept of NP-complete problems.

4 QH credit
Prerequisite: COM 1350.

Course Information

Course is offered during the Winter and Summer quarters. CS majors are guaranteed a place in class.
  • Winter 2000
  • Summer 2001
  • Course Format

    BSCS03 required course
    BSCS04 Algo & Data core
    BACS required core
    BSIS general elective

    This is a required course for BS CS majors graduating in the year 2003 and before, is an Algorithms & Data core course for BS CS majors graduating in the years 2004 and beyond and a required course for BA CS majors.

    Course Coordinators

    Professor Rajmohan Rajaraman

    Textbooks and References

    Summer 2000

    Course Goals

    Prerequisites by Topic

  • Discrete mathematics (sets, functions, elementary combinatorics)
  • Elementary data structures (arrays, linked lists, trees, hashing, priority queues)
  • Encapsulation and abstraction
  • Programming
  • Recursion and induction
  • Models of computation
  • Major Topics Covered in the Course

    Advanced algorithms, the related data structures, and their analysis:
  • Divide and conquer type of algorithms
  • Maintenance of dynamic sets
  • Greedy algorithms
  • Dynamic Programming
  • Graph traversals
  • Data Structures
  • Laboratory projects

    The homework consists primarily of assignments requiring written solutions to assigned mathematical problems.  They test problem-solving skills.  A total of 5 homeworks are typically handed out over a period of 10 weeks.  In addition, 1 or 2 programming assignments that span over 2-3 weeks are handed out.