Princess Sumaya University for Technology
Department of Computer Science
Design and Analysis of Algorithms - Spring 2016
Section 1: Mo, We @ 11:00 AM (Room IT-201)
Section 2: Su, Tue, Thu @ 10:00 AM (Room IT-201)
Download official syllabus from here.
"This course presents fundamental techniques for designing and analyzing efficient computer algorithms. Students learn how to write fast algorithms to solve various problems and how to estimate their running times before running them. Students also do programming projects in which they implement different algorithms and compare their actual running times with the theoretical estimates. The course covers general problem solving techniques including divide-and-conquer, greedy, dynamic programming, brute-force, branch-and-bound and backtracking. These techniques are applied to specific problems involving sequences, graphs, trees and numerical data. Various algorithms for solving these problems are analyzed and compared theoretically and experimentally."
- A desire to learn and a good attitude towards programming and problem solving.
Other useful books include:
We emphasize that you are encouraged to discuss with your classmates. Discussion allows for better understanding and more engagement. However, make sure not violate the above-mentioned collaboration rule. Not respecting the rules may lead to any (or all) of the following consequences (depending on the case):
Please remember that gamifying this course is not possible without a commitment to fair play and without a sense of trust between us! I hope that we will all enjoy the game!
Department of Computer Science
Design and Analysis of Algorithms - Spring 2016
Section 1: Mo, We @ 11:00 AM (Room IT-201)
Section 2: Su, Tue, Thu @ 10:00 AM (Room IT-201)
Download official syllabus from here.
Instructor Information
Dr. Ibrahim Albluwi
Email: i.albluwi@psut.edu.jo
Office: IT-309
Extension: 243
Extension: 243
Office Hours:
Sundays and Thursdays: 9:00 - 10:00
Mondays and Wednesdays: 14:00 - 15:30
Tuesdays: 9:00 - 10:00 and 11:00 - 12:00
Sundays and Thursdays: 9:00 - 10:00
Mondays and Wednesdays: 14:00 - 15:30
Tuesdays: 9:00 - 10:00 and 11:00 - 12:00
Course Description
After completing this course, you will be able to:- Perform basic asymptotic analysis of algorithms and use the appropriate notation. (We will fine tune some of what has been covered in the Data Structures course and learn more about recurrences).
- Design solutions using the Divide and Conquer technique for several basic problems. (You will be exposed to at least 6 different problems).
- Design Dynamic Programming solutions for several basic problems. (You will be exposed to around 7 different problems).
- Design Greedy solutions for several basic problems. (You will be exposed to around 5 problems)
- Design algorithms for several basic problems using the backtracking technique. (You will be exposed to around 4 problems).
- Solve basic problems that are modeled on graphs. (Examples of such problems include: Shortest Paths, Topological Sort, Minimal Spanning Trees, etc.)
- Compare between different algorithmic techniques and explain when each technique should be used.
"This course presents fundamental techniques for designing and analyzing efficient computer algorithms. Students learn how to write fast algorithms to solve various problems and how to estimate their running times before running them. Students also do programming projects in which they implement different algorithms and compare their actual running times with the theoretical estimates. The course covers general problem solving techniques including divide-and-conquer, greedy, dynamic programming, brute-force, branch-and-bound and backtracking. These techniques are applied to specific problems involving sequences, graphs, trees and numerical data. Various algorithms for solving these problems are analyzed and compared theoretically and experimentally."
Prerequisites
- Data Structures and Introduction to Algorithms (CS212).- A desire to learn and a good attitude towards programming and problem solving.
Textbook
All required material will be provided as either links to online resources or as slides and notes. However, most of the material will be based on the following book:
Thomas H. Cormen,
Charles E. Leiserson,
Ronald L. Rivest,
Clifford Stein,
Third Edition, 2009 (MIT Press).
Third Edition, 2009 (MIT Press).
- Sanjoy Dasgupta, Christos Papadimitriou and Umesh Vazirani, Algorithms, First Edition, 2006 (McGraw-Hill Education).
- Richard Neapolitan, Foundations Of Algorithms, Fifth Edition, 2014 (Jones & Bartlett Learning).
- Jon Kleinberg and Éva Tardos, Algorithm Design, First Edition, 2005 (Pearson Education).
- Steve S. Skiena, The Algorithm Design Manual, Second Edition, 2008 (Springer).
Grades Distribution
|
Coursework
In this course, there will be a variety of tasks that you can collect experience points for completing them. Your final grade out of 20% will be determined according to the number of points you collect and your rank in the class.
Please see the Coursework page in order to learn more about the different tasks and how you can collect points.
Please see the Coursework page in order to learn more about the different tasks and how you can collect points.
Collaboration Policy
Collaboration is great! We all learn by discussing with others. However, collaboration can be harmful if we abuse it.
You are encouraged to discuss with your classmates regarding any task provided that you respect the following:
- Do not discuss about any quiz question with anyone before the deadline is over.
- Never show your code to any student in the course.
- Never look at the code of any student in the course.
- Never write any piece of code to anyone in the course. This includes writing pieces of code on paper and on electronic devices.
- Never ask (or allow) anyone taking this course or not taking it to write any piece of code for you.
- Never copy and paste pieces of code from the internet or any other resource.
We emphasize that you are encouraged to discuss with your classmates. Discussion allows for better understanding and more engagement. However, make sure not violate the above-mentioned collaboration rule. Not respecting the rules may lead to any (or all) of the following consequences (depending on the case):
- A deduction of a number of experience points (see the coursework page).
- A report written and sent to the dean of the college of IT and the deanship of student affairs.
- A failing grade in the course.
We do not guarantee that everyone who does not respect these rules will be caught. However, we guarantee that everyone that is caught will be strictly penalized.
Please remember that gamifying this course is not possible without a commitment to fair play and without a sense of trust between us! I hope that we will all enjoy the game!
Attendance Policy
Attending lectures is very important for understanding the material. Please make sure to always come on time and to avoid any unnecessary absence.
According to the university laws, a student should not be allowed to enter the final exam in any of the following two situations:
Any student that arrives after taking the attendance is considered late. The reason for this policy is that arriving late disrupts the lecture since the door is just beside the white-board.
You will be awarded with experience points depending on how many lectures you miss! (more on this in the Coursework page)
According to the university laws, a student should not be allowed to enter the final exam in any of the following two situations:
- Missing 15% of the lectures without a valid excuse (8 lectures or more).
- Missing 20% of the lectures even if there is a valid excuse. If there is a valid excuse, the student is allowed to drop the course without receiving a failing grade.
- Medical Excuses attested by the university doctor.
- Excuses issued by the deanship of student affairs, the university administration or attested by the dean of the College of Computing Sciences.
Any student that arrives after taking the attendance is considered late. The reason for this policy is that arriving late disrupts the lecture since the door is just beside the white-board.
You will be awarded with experience points depending on how many lectures you miss! (more on this in the Coursework page)
No comments:
Post a Comment