CENG567 DESIGN AND ANALYSIS OF ALGORITHMS
| Course Code: | 5710567 |
| METU Credit (Theoretical-Laboratory hours/week): | 3 (3.00 - 0.00) |
| ECTS Credit: | 8.0 |
| Department: | Computer Engineering |
| Language of Instruction: | English |
| Level of Study: | Graduate |
| Course Coordinator: | Prof.Dr. MEHMET HALİT S. OĞUZTÜZÜN |
| Offered Semester: | Fall or Spring Semesters. |
Course Objectives
At the end of this course, the student will learn:
- review of basic concepts of analysis of algorithms
- review of important algorithms
- lower and upper bound teory concepts and proof of them
- a number of algorithm design approaches, such as divide and conquer, greedy design technique, dynamic programming, backtracking, branch and bound design tecniques
- amortized analysis
- NP-Complete and NP-Hard Problems
- Proof of NP-Completeness and Reducibility
- Approximation Algorithms
Course Content
Introduction to algorithms. The computational complexity of algorithms. Amortized analysis. Lower and upper bound theory. Approaches for designing algorithms: Divide-and-Conquer, Greedy Approach, Dynamic Programming, Backtracking and Branch-and-Bound. NP-Complete and NP-Hard problems. Approximation algorithms.
Course Learning Outcomes
Student, who passed the course satisfactorily will be able to:
- analyze any complex algorithm in terms of time and space efficiency
- analyze any complex problem using the lower bound theory
- design any algorthm as an efficient solution for the problem using an appropriate design technique.
- identify NP-Complete / NP-Hard problems and prove them that they are
- solve engineering/mathematical problems efficienty and anlayze them to show how efficient they are in terms of time and space
- formulate approximate algorithms for intaractable problems and show how good the solution are
Program Outcomes Matrix
| Contribution | |||||
| # | Program Outcomes | No | Yes | ||
| 1 | Competence in fundamental and advanced knowledge of hardware and software Proficiency in problem solving. | ✔ | |||
| 2 | The ability to follow the contemporary technical development, and Initiative and aptitude for self-directed learning. | ✔ | |||
| 3 | They are capable of designing, and conducting experiments at advanced level. | ✔ | |||
| 4 | The ability to design and implement systems involving hardware, software, and the interaction between the two through challenging projects. | ✔ | |||
| 5 | Analyze and compare relative merits of alternative software design, algorithmic approaches and computer system organization, with respect to a variety of criteria relevant to the task (e. g. efficiency, scalability, security). | ✔ | |||
| 6 | Strong interpersonal skills needed for working effectively in small, diverse groups on medium to large scale technical projects. | ✔ | |||
| 7 | Strong oral communication skills essential for effectively presenting technical material to an audience and strong written communication skills and the ability to write technical documents that include specification, design, and implementation of a major project. | ✔ | |||