CISC 3220 -- Analysis of Algorithms

[ General information ] [ Syllabus ] [ Homework Assignments ] [ Important Dates ]

Announcements

12/13/2016 Here are the answers to the sample exam 2 that is posted.
12/13/2016 The final exam for CISC 3220 MW12 is Wednesday, December 14, 1:00-3:00pm, in our regular room 1105N. The questions will be on the following topics:
  1. Asymptotic order and time complexity
  2. Recurrence equations (rec. trees and master thm)
  3. Sorting and Selection
  4. Graphs (representation, BFS, DFS, Prim, Kruskal, Dijstra)
  5. String Matching
  6. NP-Completeness.
11/24/2016 Here are the diagrams of the actual graphs for questions 2 and 3 on Exam 2 Spring 2009.
11/24/2016 For interest sake, read this one page article -- it is a piece of history.
11/22/2016 EXAM 2 is scheduled for MONDAY, DECEMBER 5. The following topics will be on the exam: Chapter 5: Selection (min-max, second largest, kth largest), Chapter 7: Graphs (definitions and implementations, Graph Traversals: DFS and BFS), Chapter 8: PRIM's Minimum Spanning Tree Algorithm, Dijkstra's Shortest Path Algorithm, and Kruskal's MST.
For each of the above algorithms, you must know the theoretical descripton and complexity analysis that we learned in class, as well as how to practically apply the techniques.
11/13/2016 Notes on proof of correctness for Prim's MST algorithm. The book has a longer more in-depth proof, but this one suffices for our class.
10/30/2016 Answer to summation question 1 on Sample Exam 1.
10/27/2016 I am posting a Sample exam 2 from Fall 2009 since QUICKSORT and HEAPSORT are on our Exam 1.
10/26/2016 There will be a review for the exam on Thursday, October 27 in room 4141 Ingersoll.
10/16/2016 I summarized the graph definitions that we will discuss in class in this document.
10/16/2016 Homework #5 on quicksort and heapsort is posted, and it is due on Oct 26.
10/13/2016 Here is a sample exam 1.
9/29/2016 Our first exam has been scheduled for Wednesday, November 2.

Topics include: [Chapter 1:] Analysis of time complexity, space complexity, asymptotic order, lower bounds and optimality.
[Chapter 3:] Recursion Trees and Master Thm for solving recurrence equations.
[Chapter 4:] Insertion Sort, Mergesort, Quicksort, lower bounds for sorting and Heapsort.
9/29/2016 Assignment #4 (on recursion trees and master thm) has been posted. It is due on Thursday, Oct 6.
9/29/2016 Here is a nice set of slides for the algorithms in Chapter 5 on selection (that we will be learning next class).
9/26/2016 Here is the partition algorithm that we will be looking at in class.
9/6/2016 Here is a link to a figure on order of growth that we will be looking at in class.
9/6/2016 Let me remind you that you are supposed to carefully read the textbook between class meetings. The only way you will be able to do the homework, and understand the next class is if you review the material from the previous class.
8/11/2016 Welcome to CISC 3220! Our first day of class is Monday, August 29. You may follow the links above for information about this course. Students often ask whether the textbook is required. Yes, you must purchase a textbook and keep up with the reading. I use the Baase textbook, but you may choose a different one and find the topics accordingly. I am interested in hearing feedback about students' preferences. Earlier editions of textbooks are fine.
If you are interested in internships or other kinds of employment (relating to computer science), please check out the CUNY Institute for Software Design and Development's new Career Center on the web at CISDD. This is a free service that matches current CUNY students with potential employers. To participate, you simply upload your resume information and go through a 10-15 minute interview at the Institute (at the CUNY Graduate Center in midtown). They very much want to have a lot of CUNY students participating, and they're also very eager to help you out with resume-writing and interviewing skills.