CISC 3220 -- Analysis of Algorithms

[ General information ] [ Syllabus and Calendar ] [ Homework Assignments ]

Announcements

12/13/11 The final exam for CISC 3220 MW11 is Wednesday, December 21, 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.
12/06/11 Homework 8's due date has been posponed to Monday, Dec 12.
12/1/11 EXAM 2 is scheduled for MONDAY, DECEMBER 5. The following topics will be on the exam: Chapter 4: Heapsort, Lower Bounds for Sorting 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, and Dijkstra's Shortest Path Algorithm.
For each of the above algorithms, you must know the theoretical descripton and complexity analysis, as well as how to practically apply the techniques.
11/29/11 Sample exam 2 albeit without graphs.
10/27/11 I summarized the graph definitions that we discussed in class in this document.
10/24/11 Here is a sample exam.
10/04/11 Our first exam has been scheduled for Wednesday, Ocotober 26th.

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 and Quicksort.
(lower bounds for sorting and heapsort are NOT on the exam.)
10/04/11 Assignment #4 (on recursion trees and master thm) has been posted. It is due on Wednesday, Oct 11.
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 have either the Baase or the McConnell textbook. 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 http://career.cisdd.org. 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.