Welcome to California State University, Chico -- Today Decides Tomorrow
Search for
 		 Search in
 
California State University, Chico
>> CSU, Chico Home
College of ECC Home
 
Core CSCI 650 syllabus Back to List
Previous Page Next Page
 
CSCI 650: Design and Analysis of Algorithms
(3 credit hours)

Course Objectives

  The objectives are for the student to:
  • augment their "tool box" of algorithm design techniques
  • learn how to analyze the efficiency of algorithms
  • learn about the intrinsic complexity of certain computational problems

Prerequisites

     Classified graduate standing, or faculty permission.

Catalog Description

     Algorithms from many areas of computer science will be analyzed. Topics include algorithm design techniques (such as divide-and-conquer, greedy algorithms, dynamic programming, and others), mathematical and empirical analysis of algorithms and NP-completeness.

Current Instructor

     Dr. Anne Keuneke

Current Course Website

     http://www.ecst.csuchico.edu/~amk/foo/csci650

Typical Text

     Computer Algorithms, Pseudocode , Horowitz, Sahni, Rajasekaran, Computer Science Press (W. H. Freeman Press), 1998, ISBN 0-7167-8316-9

Course Coverage

Introduction: Review of Algorithms
1. pseudocode conventions
2. induction
3. performance analysis
4. recursion

Review of Data Structures

Algorithm Types
1. divide and conquer
2. greedy method
3. dynamic programming
4. basic traversal and search
5. bactracking
6. branch-and-bound

Determistic/non-deterministic machines

Lower Bound Theory
1. oracles

Reducibility
1. Cook/Turing
2. determining power of languages/algorithms

Intractability
1. P, NP and co-NP
2. NP-complete
  • Satisfiability

3. NP-hard
  • Halting Problem
 
Computer Science | Welcome | Important Dates! | Advising | Facilities | News | Career Opportunities | Mission | Industry Involvement | Assessment Tools | Alumni | Research | BS in Computer Science | BS in Computer Information Systems | MS in Computer Science | Minor in Computer Science | Minor | Online Program
CSU, Chico:
Home | Admissions | Bookstore | Catalog | Schedule | Library | Help

This page and its contents © 2003 College of Engineering, Computer Science, & Construction Management
California State University, Chico
College of Engineering, Computer Science, & Construction Management
California State University, Chico
Chico, CA 95929-0003
530-898-5963
webmaster@ecst.csuchico.edu

Maintained by Freedom™.   Developed by Diverse Network Associates™.
Department of Computer Science Preparing Graduates to Solve 21st Century Problems