Fundamental Algorithms
CSCI-GA 1170
Wednesday 6:00-8:20
Room WWH 102
Professor Ernest Davis
Reaching Me
- phone: (212) 998-3123
- office: 329 Warren Weaver Hall
- Office hours: Tuesday 10-12 or by appointment.
- Email:
Recitation
The recitation will meet Thursday, 6:00-7:00, WWH 102. Attendance at the
recitation is strongly recommended. In any case, be sure that you
register for the recitation (section 002) as well as the class
(section 001).
The recitation instructor for the course is Azam Asl,
aabdol01@students.poly.edu.
Prerequisites: None.
Required Textbook:
Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein,
3rd edn. (Previous editions are also fine, if you can get them used
cheap.)
Topics
- Algorithmic analysis:
Correctness. Worst-case running time asymptotic
analysis. Big Oh notation. CLRS, chaps. 1-3.
- Divide-and-conquer Recurrence equations.
CLRS chap. 4.
- Sorting algorithms:
N2 sorts, Heapsort, Mergesort, Quicksort,
Radix sort. Lower bound. CLRS chaps. 6-8.
- Sets: Lists. Hash tables. Binary trees. B-trees. CLRS
chap. 10, 11, 12, 18.
- Directed graphs: Implementation. Depth-firt search. DAGS.
Shortest paths. CLRS chaps. 22,24,25.
- Undirected graphs: Minimum spanning tree. Union-find algorithm.
CLRS chaps. 21, 23.
- Algorithmic techniques: Dynamic programming.
Greedy algorithms. CLRS, Chaps. 15, 16.
- State space search/Implicit graphs: . Iterative deepening.
Class notes.
Requirements
Weekly problem sets (50%)
Final exam (50%).
Problem sets should be submitted in hard copy or by email by the start of
class on the day they are due. For email submissions, I prefer PDF,
but plain-text or Word are OK. They will be handed back and
discussed at the recitation
the next day, so they cannot be accepted late.
Class email list
Link to
the class email web page and follow the instructions there for
subscribing.
Assignments
Problem Set 1 Due June 1.
Problem Set 2 Due June 8.
Problem Set 3 Due June 15.
Problem Set 4 Due June 22.
Problem Set 5 Due June 29.
Problem Set 6 Due July 6.
Problem Set 7 Due July 13.
Problem Set 8 Due July 20.
Problem Set 9 Due July 27.
Supplementary Notes
Using Hashing for Large Sets of Large Objects
Notes on Scheduling
Final exam
The final exam will be Wednesday August 10.
Notes on the Final Exam
Sample Final Exam
Additional practice problems can be found in the department's
collection of Core Exams
Solutions to final exam
Cheating
You may discuss any of the assignments with your classmates (or anyone else)
but all work for all assignments must be
entirely your own. Any sharing or copying of assignments will be
considered cheating. By the rules of the Graduate School of Arts and Science,
I am required to report any incidents of cheating to the department.
My policy is that the first incident of cheating will result in the
student getting a grade of F for the course.
The second incident, by GSAS rules, will result
in expulsion from the University.