Back to CS Home Page |
Computer Science Course Information |
Course No. | CIS 610 |
Sections | 003, 103 |
Title | Data Structures & Algorithms |
Course Website | www.cs.njit.edu/~nassimi |
Prerequisite(s) | (1) Undergrad course on Data Str & Algorithms (CIS 505 or equivalent);
(2) Discrete Math (CIS 241 or Math 226); (3) Programming Maturity |
Instructor | David Nassimi |
Instructor Office Hours | |
Description | This is a graduate-level course on data-structures and algorithms, with an emphasis on design and analysis of algorithms. Topics include analysis techniques, worst-case/averagecase analysis, induction, recursion, recurrence relations, and divide-and-conquer design techniques; priority queues, hash tables, binary-search tress, balanced search trees (AVL tress); sorting algorithms; other
design techniques such as greedy-method and dynamic-programming; graph algorithms, and text processing algorithms. |
Topics | COURSE OUTLINE
Weeks Topic ........................................ Reading (Goodrich-Tamassia) 1 Introduction ................................. Chapter 1 Analysis Techniques 2 Induction Recursion Recurrence Relations ......................... p. 12, Sec. 4.1, 5.2 3 Divide-and-Conquer Technique and Recurrences.. Sec. 5.2 Basic Data Structures (Self-Review) .......... Ch. 2, Sec. 2.1-2.3 Linked-Lists, Stacks, Queues, Trees 4 Other Data Structures ........................ Ch. 2, Sec. 2.4-2.5 Priority Queues, Heaps Hash Tables 5-6 Search Trees ................................. Chapter 3 Binary-Search-Trees Balanced Search Trees: AVL Trees Red-Black Trees and B-Trees (self-study) 7-9 Sorting Algorithms ........................... Chapter 4 Integer-Sorting: Bucket-Sort, Radix Sort Basic Sorting Algorithms: Insertion-Sort, Bubble-Sort, Selection-Sort Mergesort, Heapsort, Quicksort Selection (Kth smallest element) 10 Algorithm Design Techniques .................. Chapter 5 Divide-and-Conquer, Greedy, Dynamic Prog. 11-13 Graph Algorithms ............................. Chapters 6, 7 Graph Definitions Graph Represenations Graph Traversals Connected Components Single-Source-Shortest-Paths (Dijkstra) All-Pairs-Shortest-Paths Algorithm Minimum-Cost-Spanning-Tree Algorithms 14 Text Processing ............................. Chapter 9 Strings and Pattern Matching Algorithms |
Text Book(s) | Michael Goodrich and Roberto Tamassia, Algorithm Design: Foundations,
Analysis, and Internet Examples, Wiley, 2002. (ISBN 0-471-38365-1) |
Time & Place | Section 003: M- 4:00-5:25 KUPF 202
W -11:30-12:55 KUPF 103 Section 103: W -6:00-9:05 TIER 113 |
Other Info | Evaluation: Assignments 30%
Midterm 35% Final 35% Exam Dates: Midterm: Week 7, Wednesday OCT. 12 (regular time & place) Final: Section 003: Time and place TBA by NJIT registrar. Section 103: Wednesday Dec. 21, 6:00-8:30 pm, TIER 113. Website: Class handouts (syllabus, assignments), announcements, and previous exams are posted. Please check the website regularly for assignments/announcements. Policies: (1) Assignments must be done by you individually. No team-work. (2) Assignments must be handed in at the beginning of the class period on the due date. (3) Late Assignments will not be acccepted. (4) Programming assignments may be done in either C, C++, or JAVA. Academic Integrity: Please familiarize yourself with NJIT Honor Code (http://integrity.njit.edu). Any evidence of dishonesty will be dealt with seriously and reported immediately to the Dean of Students. |