Coping with NP-Hardness
Lecturers and Teaching Assistants
Prof. David Peleg
Course Schedule and Location
Monday, 09:15 - 11:00, Ziskind, Rm 1
Field of Study, Course Type and Credit Points
Mathematics and Computer Science: Lecture; Elective; Regular; 2.00 points
Basic (undergraduate level) course in algorithms.
Attendance and participation
Scheduled date 1
Scheduled date 2
Estimated Weekly Independent Workload (in hours)
The course will discuss NP-hard problems and basic methods for dealing with them, including exact solution methods such as divide and conquer, direct search with eliminations and dynamic programming, approximation algorithms, approximation methods such as the greedy algorithm and ILP relaxations (" randomized rounding "), and fixed-parameter tractability.
Upon successful completion of this course students should be able to:
- Discuss some key notions and principles related to NP hard problemsץ
- Demonstrate knowledge of some of the central problems in the area and the various approaches to tackling them, become familiar with some of the basic algorithmic techniques of the area, and get exposed to modern research in the field.