Algorithms Syllabus

THE HASHEMITE UNIVERSITY Faculty of Engineering Computer Engineering Department (CPE) Course Syllabus Fall 2013 Semester...

1 downloads 309 Views 732KB Size
THE HASHEMITE UNIVERSITY Faculty of Engineering Computer Engineering Department (CPE) Course Syllabus Fall 2013 Semester Course Title: Algorithms Department: Computer Engineering (CPE) Prerequisite(s): Discrete Math (110101152), Data Structure (110408213)

Course Number: Designation:

110408300 Compulsory

Instructor: Dr. Khalil Yousef Instructor's e-mail: [email protected] Office Hours: Currently by email request Lecture Time: Sun/Tues/Thur 1:00 - 2:00 pm Web Site: TBD

Instructor's Office:

TBD

Course description: This course is an introductory course to the design, implementation and analysis of computer algorithms. Topics covered include but not limited to the growth of functions, the time complexity of algorithms, recurrence relations and their solutions, probabilistic analysis and randomized algorithms, the design and analysis of various sorting algorithms (insertion, merge, quick, and heap sort), graph searching algorithms (breadth-first and depth-first search), spanning trees, and NP completeness. Course objectives:  Provide fundamental knowledge regarding the design and analysis of computer algorithms.  Provide tools to analyze and compare the performance of algorithms (space and time).  Learn to prove the correctness of algorithms.  Emphasize classes of problems that can be solved by computers. Textbook(s): Introduction to Algorithms, second edition by Cormen, Leiserson, Rivest, and Stein. The MIT Press. ISBN #0-07-013151-1 (2001). Course Outline: I intend to follow the textbook table of contents as a course outline. I plan to cover most of chapters 1 to 8, 10, 22 to 24, and chapter 34, along with the mathematical background in the appendices (A,B,C). Typically, these appendices and chapters cover summations, sets, counting and probability, order of growth, recurrences, analysis of randomized

Class Room: TBD

algorithms, sorting algorithms (e.g., heap sort, quick sort, etc.), graph algorithms (depth-first and breadthfirst search, minimum spanning trees, and shortest paths algorithms), and NP-completeness. Additional topics will be covered if time allows (dynamic programming, greedy algorithms, amortized analysis). Reading Assignments: You are expected to find the related reading in the text on your own. I expect all the chapters listed above under Course Outline to be read by students as they are covered in class. I may test any material covered in these chapters once the relevant topic has appeared in class lectures. Please ask me if it is unclear whether a chapter or section has been covered. Office Hours: I will hold office hours each week but this is to be determined later on (Please email me advance notice if you plan to attend so I can manage my time during weeks when no one plans to come). Currently, I will be holding my office hours only by email request. Exams: There will be two IN-CLASS midterm exams (First and Second) and one comprehensive final exam will be held at the end of the semester as scheduled by the University Registrar.  The First exam date is Sunday Oct 13, 2013  The Second exam date is Sunday Nov 24, 2013 Both of the first and second exams will be held in the same class room.

Page 1 of 3

If for any reason you cannot make one of the announced times, you must let me know immediately. 

   

All exams are CLOSED-BOOK and closed notes. You must solve the exam problems yourself, without any help (knowing or unknowing) from any other student. You must not seek any knowledge in advance of the test questions (beyond that given in class), and must report any violation of these rules by any student that you are aware of. You must not allow any other student access to your solutions during an exam. If the seating situation makes this difficult please inform me beforehand. Exams will cover the assigned reading materials and discussed materials in the lectures. Exam solutions will be discussed in class. Written solutions will NOT be distributed. All calculations must be done by hand, with all work shown, in order to receive full credit. The final exam will be held during the university examination period (21/12/2013 2/1/2014). The exam will include questions from all the topics discussed in class. The final exam must be written in pen, closed-book, no calculators, no electronic translators, and no scrap paper.

Grade Allocation:  25 % Each of two midterm exams.  50 % Final exam Borderline grades will be resolved based upon classroom participation and homework performance. Regrade Requests: Exams may be submitted for regarding up to one week after they are returned to the class. To request a regrade, write an explanation of your request on the front of the exam and attach it to the assignment or exam, then give the assignment to me. Extra Credit: There will be no extra credit projects apart from those assigned to the entire class as part of the regular homework assignments and/or exams. From time to time, a limited amount of extra credit may be available as part of a regular assignment or exam. Such extra credit may improve your grade but will not hurt the grades of those who chose not to do it. (Initial grade assignment is done before any extra- credit is taken into account).

Administrative Information: All current information about the course (e.g. office hours, exam dates, etc.) is subject to change at any time. Changes will be announced in class, as well as emailed to you. PLEASE SEND EMAIL TO ME IMMEDIATELY TO BE ADDED TO THE CLASS EMAIL LIST. Homework/Projects: Homework will be assigned regularly, with due dates at which solutions will be made available. Written homework will be collected but not graded! Collected homework will be used to resolve borderline grades during grade assignment. You are responsible to yourself to learn the material by performing the homework in a timely manner. Homework will be due at the beginning of class and late homework will not be accepted. Discussion of and collaboration on homework problems is encouraged. Each student is responsible to ensure that they understand/learn the material by whatever process works for them. Homework is not a direct part of the evaluation process in this course. General Behavior and Cheating: I expect you to behave like a professional. A professional engineer is polite, considerate and respectful of others. It is rude, inconsiderate, and disrespectful to your fellow students and to the professor to talk in class. No one can learn if you are chatting to your neighbor! I expect you to maintain the highest standard of academic honesty and integrity in your work in this class. Unambiguous cases of cheating will result in an F for the course as will repeated suspect work. Any suspect work may be given a zero. Allowing someone to cheat from your work is as serious a violation as cheating from someone else's work. I also expect you to hold both your solution and the solution to each homework and exam in confidence and not to share or distribute these solutions after the end of the course. Feedback: I actively solicits positive and negative feedback from students throughout the course. If you have a complaint about how the course is taught or organized, or constructive feedback on what would work better for you, please send e-mail feedback to [email protected]. Feedback will in no way negatively influence your grade—thoughtful feedback, both positive and negative, is much appreciated. Negative feedback is particularly valuable in helping improve the course.

Page 2 of 3

Course Plan Week no. 1 2 3 4 5

Topic Review (summations, sets, counting and probability) Introduction

chapter Appendices A,B,C 1,2

Order of growth

3

Recurrences

4

Probabilistic Analysis and Randomized Algorithms

5

First Exam (Sunday Oct 13, 2013)

6

‫(عيد األضحى‬Monday Oct 14 - Thursday Oct 17, 2013)

7

Heapsort

6

8

Quicksort

7

9

Sorting in Linear Time (Note: Tuesday might be a holiday- Hijri new year)

8

10

Elementary Data Structures

10

11

Elementary Graph Algorithms

22

12 13 14, 15 16

Second Exam (Sunday Nov 24, 2013) Minimum Spanning Trees

23

Single-Source Shortest Paths

24

NP Completeness

34

Primitive Introduction to Dynamic Programming + Greedy Algorithms

15,16

Final Exam (21/12 - 2/1, 2013)

Page 3 of 3