Course Identification

Title:

Coping with NP-Hardness

Code:

20204141

Lecturers and Teaching Assistants

Lecturers:

Prof. David Peleg

TA's:

N/A

Course Schedule and Location

Year:

2020

Semester:

First Semester

When / Where:

Monday, 09:15 - 11:00, Ziskind, Rm 1

First Lecture:

04/11/2019

Field of Study, Course Type and Credit Points

Mathematics and Computer Science: Lecture; Elective; Regular; 2.00 points

Comments

N/A

Prerequisites

Basic (undergraduate level) course in algorithms.

Restrictions

Participants:

60

Language of Instruction

English

Attendance and participation

Expected and Recommended

Grade Type

Numerical (out of 100)

Grade Breakdown (in %)

Final:

100%

Evaluation Type

Examination

Scheduled date 1

Date / due date

11/02/2020

Location

Ziskind, Rm 1

Time

0915-1115

Remarks

N/A

Scheduled date 2

Date / due date

09/03/2020

Location

Ziskind, Rm 1

Time

0915-1115

Remarks

N/A

Estimated Weekly Independent Workload (in hours)

1

Syllabus

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.

Learning Outcomes

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.

Reading List

N/A

Website

N/A