COMPSCI170
Download as PDF
COMPSCI 170 - Efficient Algorithms and Intractable Problems
Subject
COMPSCI
Course Number
170
Department
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 Units
4
Maximum Units
4
Grading Basis
Default Letter Grade; P/NP Option
Method of Assessment
Written Exam
Instructors
Demmel, Papadimitriou, Rao, Wagner, Vazirani
Prerequisites
COMPSCI 61B and COMPSCI 70.
Repeat Rules
Course is not repeatable for credit.
Credit Restriction Courses. Students will receive no credit for this course if following the course(s) have already been completed.
-
Formats
Lecture, Discussion
Term
Fall and Spring
Weeks
15 weeks
Weeks
15
Lecture Hours
3
Lecture Hours Min
3
Lecture Hours Max
3
Discussion Hours
1
Discussion Hours Min
1
Discussion Hours Max
1
Outside Work Hours
8
Outside Work Hours Min
8
Outside Work Hours Max
8
Term
Summer
Weeks
8 weeks
Weeks
8
Lecture Hours
6
Lecture Hours Min
6
Lecture Hours Max
6
Discussion Hours
2
Discussion Hours Min
2
Discussion Hours Max
2
Outside Work Hours
16
Outside Work Hours Min
16
Outside Work Hours Max
16