COMPSCI170
Download as PDF
Efficient Algorithms and Intractable Problems
Subject
COMPSCI
Course Number
170
Course Level
Undergraduate
Course Title
Efficient Algorithms and Intractable Problems
Course Description
Concept and basic techniques in the design and analysis of algorithms; models of computation; lower bounds; algorithms for optimum search trees, balanced trees and UNION-FIND algorithms; numerical and algebraic algorithms; combinatorial algorithms. Turing machines, how to count steps, deterministic and nondeterministic Turing machines, NP-completeness. Unsolvable and intractable problems.
Minimum
4
Maximum
4
Grading Basis
Default Letter Grade; P/NP Option
Method of Assessment
Written Exam
Instructors
Demmel, Papadimitriou, Rao, Wagner, Vazirani
American Cultures Requirement
No
Reading and Composition Requirement
None of the Reading and Composition Requirement
Prerequisite
Complete ALL of the following Courses:
Repeat Rules
Course is not repeatable for credit.
Credit Restriction Courses. Students will receive no credit for this course if the following the course(s) have already been completed.
-
Formats
Lecture, Discussion
Term
Fall and Spring
Duration (in weeks)
15
Minimum Hours
3
Maximum Hours
3
Minimum Hours
1
Maximum Hours
1
Outside Work Hours Min
8
Maximum Hours
8
Term
Summer
Duration (in weeks)
8
Minimum Hours
6
Maximum Hours
6
Minimum Hours
2
Maximum Hours
2
Outside Work Hours Min
16
Maximum Hours
16