**Term and Credits**

Fall 2015-2016

3 Credits

**Room and Time**

Tuesday, Thursday 12:30pm - 1:50pm

UC 153

**Instructor**

Mark Boady

*Electronic Mail Address:* mwb33@drexel.edu

*Office:* University Crossings 100A untill construction finishes on UC138

*Extention:* 215-895-2347

*Office Hours:* Tuesday 2-5pm, Wednesday 2-3pm

**Teaching Assistant(s)**

No TA Assigned

**Course Description**

This course covers techniques for analyzing algorithms, including: elementary combinatorics, recurrence relations, and asymptotic analysis; data structures such as hash tables, red-black trees, B-trees, binomial and Fibonacci heaps, union-find trees; sorting algorithms and elementary graph algorithms.

**Course Objective and Goals**

- Learn to analyze algorithms and data structures
- Learn the fundamental algorithms and data strutures
- Learn how to adapt these algorithms and data strutures to solve new problems./li>
- Learn the importance of finding efficient ways to solve problems.

**Audience and Purpose within Plan of Study**

This is a track computer science course required by Computer Science students taking the Data Structures and Algorithms Track.

**Prerequisites**

CS260, CS270, Math 221

**What Students Should Know Prior to this Course**

- Students should have advanced experience programming in mutliple languages
- Familiarity with basic data structures such as trees, arrays, and graphs.
- Familarity with Descrete Mathematics and working with series summations.

**What Students will be able to do upon Successfully Completing this Course: Statement of Expected Learning**

- Students will be able to analyze algorithms.
- Students will understand a set of fundamental algorithms and how to apply them.
- Students will be able to determine what aglorithms and data structures to use for efficient problem solving.

**Textbook**

Introduction to Algorithms, 3rd Edition

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein

ISBN-10: 0262033844

ISBN-13: 978-0262033848

See it on Amazon

See it at the Bookstore

*Note: If you choose to use the Second Edition, it is your responsibility to ensure all content is the same. Copies of Third Edition are available in the CLC and Library. You WILL NOT get a free pass for answering the wrong questions*

**Grading and Policies**

- Written Assignments (4) 30%
- Weights for HW grade
- Homework 0: 10%
- Homework 1: 30%
- Homework 2: 30%
- Homework 3: 30%

- Programming Assignments (2) 20%
- Weights for PA Grade
- Programming Assignment 1: 50%
- Programming Assignment 2: 50%

- Midterm Exam 20%
- Final Exam 30%

Final grades will be determined by your total points weighted according to this distribution. Grades may be curved but are generally computed via the formula below. It may be modified at the instructor's sole discretion, but letter grades will generally not be lower than those shown here.

- A range (A+, A, A-) is a course average [90, 100)
- B range is a course average [80, 90)
- C range is a course average [70, 80)
- D range is a course average [60, 70)
- F range is a course average [0, 60)

**Academic Honesty Policy**

The CCI Academic Honesty policy is in effect for this course. Please see the policy at http://drexel.edu/cci/resources/current-students/undergraduate/policies/cs-academic-integrity/ .

**Submitting Assignments**

Assignments will be submitted to learning.drexel.edu by 11:59PM on the date they are due. Grades will be reported via learning.drexel.edu.

Labs, and assignments, and exams will be returned on a regular basis to provide feedback to students.

Each student has 2 late days they may use at any time during the term. No penalty will be given for assignment submitted using these days. The student **MUST** email the Professor **BEFORE** the due date for the assignment and to inform him that a late day is being used.

Once both late days have been used, no additional late assignments will be accepted. Exceptions to this requirement may be given at the Professor's sole discretion.

Late days may be used together, to submit one assignment two days late or seperately to submit two assignments 1 day late each. Students may not break up a late day, for example submiting one assignment 6 hours late and one 18 hours late. Requesting use of a late day gives the student 24 extra hours from the deadline to submit the assignment

**Topics**

- Analysis of Algorithms
- Sorting Algorithms
- Sorted Structures (Heaps, Binary Trees, ...)
- Graph Algorithms (DFS, BFS, MST, ...)
- String Matching

**Tentative Course Schedule**

Please see the appropriate assignment, lab, and/or project webpages for a tentative schedule of course deliverables.

**Computer/Software Help**iCommons: http://drexel.edu/cci/about/our-facilities/rush-building/iCommons/**University Policies**In addition to the course policies listed on this syllabus, course assignments or course website, the following University policies are in effect:

- Academic Honesty: http://www.drexel.edu/provost/policies/academic_dishonesty.asp
- Judicial Affairs Academic Integrity: http://drexel.edu/studentlife/community_standards/facultystaff/integrity/
- Official Final Exam Schedule: http://www.drexel.edu/registrar/scheduling/exams/
- Students with Disability Statement: http://drexel.edu/oed/disabilityResources/overview/
- Course Drop Policy: http://www.drexel.edu/provost/policies/course_drop.asp
- The instructor may, at his/her/their discretion, change any part of the course during the term, including assignments, grade brakdowns, due-dates, and the schedule. Such changes will be communicated to students via the course web site Announcements page. This page should be checked regularly and frequently for such changes and announcements. Other announcements, although rare, may include class cancellations and other urgent announcements.
- Drexel Student Learning Priorities: http://www.drexel.edu/provost/irae/assessment/outcomes/dslp/

Week | Topic | Reading | Assignment |

1 | Insertion Sort and Analysis | Chapters 2-3 Recommended: Appendix A |
HW0 Due Sunday Sept 27 11:59pm HW1 Assigned |

2 | Mergsort and Quicksort | Chapters 4 and 7 | |

3 | Heaps and Queues | Chapter 6 | HW 1 Due Sunday Oct 11 11:59pm HW 2 Assigned |

4 | Search Trees and Selection | Chapters 12 and 9 | |

5 | Red Black Trees | Chapter 13 | HW2 Due Sunday Oct 25 11:59pm PA1 Assigned |

6 | Midterm | ||

7 | Introduction to Graphs DFS and BSF | Chapter 22 | PA1 Due Sunday Nov 8 11:59pm PA2 Assigned |

8 | Minimum Spanning Trees | Chapter 23 | |

9 | String Matching | Chapter 32 | PA2 Due Sunday Nov 22 11:59pm HW3 Assigned |

10 | Amortized Analysis (Thanksgiving) | Chapter 17 | |

11 | Amortized Analysis Review |
Chapter 32 | HW3 Due Sunday Dec 6 11:59pm |

12 | Final |