ECS 122B ALGORITHM DESIGN AND ANALYSIS (4 units)
Lecture: 3 hours
Discussion: 1 hour
Theory and practice of hard problems and problems with complex algorithmic solutions. NP-completeness, approximation algorithms, randomized algorithms, dynamic programming, and branch and bound. Students do theoretical analysis, implementation and practical evaluations. Examples from parallel, string, graph, and geometric algorithms.
Prerequisite: ECS 122A; (ECS 060 or ECS 034 or ECS 036C)
Credit restrictions, cross listings: None
Summary of course contents
- NP-completeness theory and implications for algorithm design.
- Examples of polynomial time reductions.
- Graph algorithms: network flow, min-cost flow, applications of network flow.
- Approximation algorithms.
- Randomized algorithms.
- Dynamic programming and practical speedups.
- Branch and bound methods for hard problems.
- Computational studies of chosen algorithms and implementations. Emphasis on time versus space versus programming simplicity. What methods really work in practice versus theory. Use of timing and profiling tools.
Goals: Students will: (1) learn techniques and viewpoints to identify and handle computationally hard problems, problems with complex algorithmic solutions; and (2) learn to evaluate the practical effectiveness of these methods
- Jon Bentley, Programming Pearls, Addison-Wesley, second edition, 1999.
- J. Kleinberg and É. Tardos, Algorithm Design, Addison-Wesley, 2005.
This class will use workstations as well as home machines. Part of the class will involve extensive computer usage.
Students will complete two to three large evaluations of competing algorithms or implementations.
Engineering Design Statement:
This course is heavily design oriented, exploiting both formal algorithm design methods and practical implementation.
ABET Category Content:
Engineering Science: 1 unit
Engineering Design: 2 units
Science & Engineering
Overlap: NP-completeness is also covered in course 120
History: Reviewed 2018.9.7 (CSUGA): prerequisites updated to include new lower division ECS series courses.2012.09.28 (C. Martel): Added one-hour discussion (incorrectly entered into ICMS without one); topics and textbooks updated; tiny rewording of catalog description. Prior version from C. Martel goes back to October 1996.
|1||X||an ability to apply knowledge of mathematics, science, computing, and engineering|
|2||X||an ability to design and conduct experiments, as well as to analyze and interpret data|
|3||X||an ability to design, implement, and evaluate a system, process, component, or program to meet desired needs, within realistic constraints such as economic, environmental, social, political, ethical, health and safety, manufacturability, and sustainability|
|4||an ability to function on multi-disciplinary teams|
|5||X||an ability to identify, formulate, and solve computer science and engineering problems and define the computing requirements appropriate to their solutions|
|6||an understanding of professional, ethical, legal, security and social issues and responsibilities|
|7||an ability to communicate effectively with a range of audiences|
|8||the broad education necessary to understand the impact of computer science and engineering solutions in a global and societal context|
|9||X||a recognition of the need for, and an ability to engage in life-long learning|
|10||knowledge of contemporary issues|
|11||X||an ability to use current techniques, skills, and tools necessary for computing and engineering practice|
|12||X||an ability to apply mathematical foundations, algorithmic principles, and computer science and engineering theory in the modeling and design of computer-based systems in a way that demonstrates comprehension of the tradeoffs involved in design choices|
|13||an ability to apply design and development principles in the construction of software systems or computer systems of varying complexity|