COMPSCI 161 Design and Analysis of Algorithms (2014-2015)

COMPSCI 161 Design and Analysis of Algorithms

(Required for CSE.)
Catalog Data:

COMPSCI 161 Design and Analysis of Algorithms (Credit Units: 4) Techniques for efficient algorithm design, including divide-and-conquer and dynamic programming, and time/space analysis of algorithms. Fast algorithms for problems applicable to networks, computer games, and scientific computing, such as sorting, shortest paths, minimum spanning trees, network flow, and pattern matching. Prerequisite: (I&C 23 or CSE 23 or I&C SCI 46 or CSE 46 and I&C SCI 6B and I&C SCI 6D and MATH 2B. I&C SCI 23 with a grade of C or better. CSE 23 with a grade of C or better. I&C SCI 46 with a grade of C or better. CSE 46 with a grade of C or better. . Same as CSE 161. (Design units: 0)

Required Textbook:
. Edition, , 1969, ISBN-13 978-0262533058 .

Recommended Textbook:
None
References:
None
Coordinator:
Michael Dillencourt and Dan Hirschberg
Relationship to Student Outcomes
This course relates to Student Outcomes: CAC a, EAC a, EAC b.
Course Learning Outcomes. Students will:

1. Use recursion and dynamic programming to design algorithms. (CAC a)

2. Analyze time complexity of algorithms. (CAC a, EAC a, EAC b)

Prerequisites by Topic

Data structures, discrete mathematics, and calculus.

Lecture Topics:
  • Introduction (Week 1)
  • Searching, sorting, lower bounds (Week 2, 3)
  • Divide-and-conquer (Week 4, 5)
  • Dynamic programming (Week 6, 7)
  • Graph algorithms (Week 8, 9)
  • Other topics (Week 10)
Class Schedule:

Meets for 3 hours of lecture and 3 hours of discussion each week for 10 weeks.

Computer Usage:

None.

Laboratory Projects:

None.

Professional Component

Contributes toward the Computing Topics experience.

Design Content Description
Approach:

None.

Lectures: 0%
Laboratory Portion: 0%
Grading Criteria:
  • Homework: 10%
  • Quizzes: 20%
  • Midterm Exams: 30%
  • Final Exam: 40%
  • Total: 100%
Estimated ABET Category Content:

Mathematics and Basic Science: 0.0 credit units

Computing: 4.0 credit units

Engineering Topics: 4.0 credit units

Engineering Science: 4.0 credit units

Engineering Design: 0.0 credit units

Prepared:
May 21, 2014
Senate Approved:
May 15, 2013
Approved Effective:
2013 Fall Qtr