Home

Schedule
  & Notes

Syllabus

Resource

Course Description: This course teaches techniques for the design and analysis of efficient algorithms, emphasizing methods useful in practice. We will look at general techniques (e.g., divide-and-conquer, dynamic programming, graph algorithms), as well as specific problem areas (e.g., sorting, searching, polynomial and matrix calculations). We will also look at issues of intractability, i.e., a discussion of the classes P (problems solvable in polynomial time) and NP (problems for which a conjectured solution can checked in polynomial time), the class of NP-complete problems, and the famous open problem of whether P=NP or not.

Prerequisite: CISC2200 (Data Structure), and CISC2100/CISC2110 (Discrete Structure II and lab) or Math 2001, Discrete Mathematics

Topics covered:

• Algorithm Analysis, Big-O notation
• Divide and Conquer paradigm/algorithms, Master Theorem
• Sorting: lower bound, O(n^2) sorting algorithms, merge sort, quicksort, radix sort, heapsort
• Hash table
• Graph traversal algorithms, minimal spanning tree algorithms, shortest distance path algorithms
• Dynamic programming paradigm and algorithms
• Classes P and NP problems

Reference Textbooks:

• (CLR) T. Cormen, C.E. Leiserson, R. L. Rivest, Introduction to Algorithms (MIT Press) (Link to Amazon entry)
• (DPV) Dasgupta et al., Algorithms (McGraw-Hill, 2006) (link to pdf).
• (Cormen)T. H. Cormen Algorithms Unlocked, MIT Press

Lectures: Tuesday/Friday, 11:30-12:45pm, JMH 331

Instructor: Dr. Xiaolan Zhang

• Email: xzhang at fordham.edu
• Office: JMH 340A
• Phone: 718-817-4484
• Office hours: Tuesday/Friday 10-11am, Zoom office hour signup here

Policy:

• Attendance: Attendance of lecture and lab section is mandatory. Please refer to Fordham's policy on class attendance. The total number of absence (excused or unexcused absences) cannot exceed four.

• Use of electrnoic device:You may NOT use laptops, tablets, or mobile phones during lectures.

• Expectation: Students are expected to spend five to eight hours outside of class each week in the assigned reading, homework and lab projects. Students are expected to read the assigned chapter of the textbooks (mostly from CLR and DPV) before the class.

• Assignments: There will be around one assignment every 1-1.5 week, either programming assignments or written assignments. No late submission is accepted unless you have asked and are granted an extension (no more than one week) for reasons such as illness, extremely heavy workload or other reasons. The maximum number of extensions per person is three.

• Extra Credits: No extra credits opportunity will be given after final exam.

• Academic Integrity: You should only hand in your own work for assignments (written or programming). Copying solutions from others, or from the Internet will be penalized as violation of academic integrity. Equally important, you should not let other students copy your solutions to assignments. Please refer to the University's policy on Academic Integrity at http://tinyurl.com/fordham-academic-integrity.

• Written/Programming Assignments (every 1-1.5 week): 30%
• Participation/Attendance: 10%
• Quizzes (weekly):10%
• Midterm: 25%
• Final Exam: 25%