Course FormatCourse Goals
Textbooks and References
Prerequisites by Topic
Major Topics Covered in Course
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 is offered during the Winter and Summer quarters. CS majors are guaranteed a place in class.
Winter 2000 Summer 2001
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.
Professor Rajmohan Rajaraman
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
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
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.