Course module NWI-IBC028 Credits (ECTS) 3 Category BA (Bachelor) Language of instruction English Offered by Radboud University; Faculty of Science; Informatica en Informatiekunde; Lecturer(s) Coordinator prof. dr. J.H. Geuvers Other course modules lecturer Contactperson for the course prof. dr. J.H. Geuvers Other course modules lecturer Lecturer prof. dr. J.H. Geuvers Other course modules lecturer Lecturer D. Rodrigues do Vale, MSc Other course modules lecturer Lecturer prof. dr. H. Zantema Other course modules lecturer Academic year 2019 Period KW3-KW4   (03/02/2020 to 30/08/2020) Starting block KW3 Course mode full-time Remarks - Registration using OSIRIS Yes Course open to students from other faculties Yes Pre-registration No Waiting list No Placement procedure -

	Aims Be able to analyze efficiency of various algorithms and be able to prove NP-completeness of several decision problems. Content Complexity is about efficiency of algorithms. On the one hand methods are presented to establish this efficiency  for concrete algorithms, in particular by analyzing and solving underlying recurrence relations.  On the other hand for various problems existence of efficient algorithms is argued to be unlikely by proving NP-completeness.   Level Presumed foreknowledge NWI-IBC027 Algoritmen en Datastructuren Test information Dit vak wordt afgesloten met een schriftelijk tentamen. Het is een 'gesloten boek' tentamen, dat wil zeggen dat er geen meegebracht materiaal (boeken, aantekeningen) bij gebruikt mogen worden. Specifics Topics Topics: • Analysis of the efficiency of algorithms. • Master method for divide and conquer. • Becoming acquainted with new algorithms where such analysis plays a role, in particular geometric algorithms. • P and NP classes. • SAT as a basis for NP-completeness. • Examples of proofs for NP-completeness. Test information This course is completed by means of a written exam. It is a ' closed book' exam, which means that no books, notes or other materials may be used during the exam. Prerequisites NWI-IBC027 Algorithms and Datastructures
	Required materials Book Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, MIT Press, Third Edition, 2009 Material not covered by this book has been collected in own lecture notes. Instructional modes Course Attendance Mandatory Yes Exam Q4 Lecture Attendance Mandatory Yes Resit Exam Q4 Tutorial Attendance Mandatory Yes Zelfstudie Tests Final grade Test weight 1 Test type Exam Opportunities Block KW3, Block KW4