Final status: December 20, 2005 (no further updates of this web page are planned)

Brief info about grading for the final (where to find the grade)

NEW! Thanks for taking the course!!!

NEW! Happy Holidays and Happy New Year!

 

CIS 610: »Data Structures and Algorithms«

Fall 2005

Section 101 (3 credits)
  

Instructor:

Dr. Artur Czumaj

Office:  4413 (GITC Building, 4th floor)
Tel.:   (973) 596-3369
Fax:   (973) 596-5777
EMail:  czumaj@cis.njit.edu
WWW:  http://www.cis.njit.edu/~czumaj/

Schedule:

Class hours  Tuesday  6:00pm - 9:05pm
Room: KUPF 117


Office Hours:		   Tuesday     4:00pm - 5:25pm
(but no office hours after December 12, 2005) Thursday   12:15pm - 1:40pm

Contents:

The main aim of the course is to teach students to understand algorithms and data structures. We will discuss algorithms and data structures for most fundamental problems. For those problems we shall focus on the design of efficient algorithms and the use of proper data structures. Some issues of the analysis of the algorithms (like correctness, running-time analysis, etc.) will be also covered.

From the NJIT graduate course catalog: Intensive study of the fundamentals of data structures and algorithms. Presents the definitions, representations, processing algorithms for data structures, data structures, algorithms and their applications including linked lists, various tree organizations, hash tables, strings, storage allocation, algorithms for searching and sorting, and a selected collection of other algorithms. Programs are assigned to give students experience in algorithms, data structure design and implementation.

Prerequisite:

  1. CIS 114 (Introduction of Computer Science II), or CIS 505, or equivalent
  2. Math 226 (Discrete Math)

Contact the instructor immediately if you didn't take any of these courses.

Additionally, students must be able to program in either C++ or Java and to understand well programs written in any of these two programming languages.

Grading and Policies:

  • Grading will be based on homework assignments, two large programming assignments, an in-class midterm, and a final.

  • Grading policy:
    • Write Assignments 10%-15%
    • Programming Assignments 25%-30%
    • Midterm 25%
    • Final 35%

  • Programming assignments must be done either in C++ or in Java.

  • You must do all assignments individually. No teamwork.

  • Writing assignments should be submitted a week after being assigned. No late submissions. Programming assignments are for several weeks.

  • Hand in all assignments at the beginning of the class period on the due date.

  • Two large programming assignments.

  • The work you turn in must be your own personal work, composed and written by you (unless stated very clearly otherwise). If you discuss a problem with a fellow student, you must mention this clearly in your homework (name the fellow student before the solution of the problem in question). Your work will then be compared to the other student's work to verify that your solution was written by you and reflect your own personal effort. If you don't report it, it will be considered a violation of the course rules, as described in the General Collaboration Policy section. (Collaboration of this kind is not allowed in the midterm and final exams.)

  • Cheating: it is surprisingly easy to detect when students are not doing their own work. Working with others on the assignments does not mean dividing the problems among you, and then swapping the answers.

  • The NJIT Honor Code will be upheld. Any violations will be brought to the immediate attention of the Dean of Students.

  • Link to the Departamental course web page with syllabus.

Contents:

The main aim of the course is to teach students to understand algorithms and data structures. We will discuss algorithms and data structures for most fundamental problems. For those problems we shall focus on the design of efficient algorithms and the use of proper data structures. Some issues of the analysis of the algorithms (like correctness, running-time analysis, etc.) will be also covered.

From the NJIT graduate course catalog: Intensive study of the fundamentals of data structures and algorithms. Presents the definitions, representations, processing algorithms for data structures, data structures, algorithms and their applications including linked lists, various tree organizations, hash tables, strings, storage allocation, algorithms for searching and sorting, and a selected collection of other algorithms. Programs are assigned to give students experience in algorithms, data structure design and implementation.

Course outline / topics to be covered (tentative):

  • General introduction:
    • what is an "algorithm design"
    • what are "data structures"
    • what does it mean to "analyze an algorithm"; worst-case and average-case analysis
    • we shall learn about techniques, tools, tricks plus a necessary information about the complexity issues
  • Analysis Techniques
    • Induction, Recursion
    • Recurrence Relations
  • Basic Data Structures
    • Abstract Data Types
    • Linked List
    • Stacks
    • Queues
  • Trees
    • Tree Traversals
    • Huffman Codes
    • Priority Queues, Heaps
    • Search Trees
      • Binary Search Trees
  • Hashing
  • Searching Algorithm
    • Sequential Search
    • Binary Search
  • Sorting Algorithms
    • Basic Algorithms
      • Insertion Sort
      • Bubble Sort
      • Selection Sort
    • Integer Sorting
      • Bucket Sort
      • Radix Sort
    • Advanced Algorithms
      • Merge Sort
      • Heap Sort
      • Quick Sort
  • Graph Algorithms
    • Graph Traversals
    • Shortest Path Problems
    • Minimum Spanning Tree
  • Algorithm Design Techniques
    • Divide and Conquer
    • Greedy Method
    • Dynamic Programming

References:

Textbook:

  • Michael T. Goodrich and Roberto Tamassia »Algorithm Design Foundations, Analysis, and Internet Examples«, John Wiley & Sons, Inc. 2002, ISBN 0-471-38365-1.

Additional references:

  • Cormen, Leiserson, Riverst, and Stein, Introduction to Algorithms, McGraw-Hill (2nd edition).
  • Aho, Hopcroft, and Ullman, Data Structures & Algorithms, Addison-Wesley, 1987
  • S. Sahni, Data Structures, Algorithms and Applications in C++, McGraw-Hill, 1998.

Homework Assignments, Programming Assignments, and Exams:

Specific contents:

  1. (9/6/05) First class
    • Discussion of the syllabus, requirements, topics to be covered, textbooks.
    • General introduction:
      • what is "algorithm design"
      • what are "data structures"
      • what does it mean to "analyze an algorithm"; worst-case and average-case analysis
    • Algorithms complexity and how to measure the running time of an algorithm.
    • "Big-Oh" notation (Big-Oh, Big-Omega, and Big-Theta).
    • Suggested reading: Chapter 1 in the textbook

  2. (9/13/05)
    • Searching a set for a given element
      • Problem definition.
      • Basic algorithm using a linked list as input representation; running-time is O(n).
      • Basic algorithm using array representation of the input set; running-time is O(n).
      • Binary search: what we can gain if the input is sorted:
        • Basic iterative algorithm.
        • Detailed proof of correctness of the binary search algorithm.
        • Running time of the binary search algorithm: O(log n).
        • Recursive version of binary search algorithm.
        • Recursion for the running time of the recursive binary search: T(n) = O(1) + T(n/2).
        • Basic strategies to solve recurrences:
          • Solving merge-sort recurrence: T(n) = O(n) + 2 T(n/2).
          • Expansion/unfolding method.
          • Recursion tree.
          • For more details, see Chapter 5 in the textbook.
    • Priority queues:
      • Definition.
      • Basic implementations of heaps using arrays:
        • one implementation requires O(1) time for EnQueue and (n) time for DeQueue,
        • another implementation requires O(n) time for EnQueue and only O(1) time for DeQueue.
      • Using prority queues for sorting.
      • Selection Sort - an implict use of priority queues (sorting algorithm that requires O(n2) time).
    • Heaps and priority queues.
    • Suggested reading: Chapter 2 in the textbook (in the class we will not discuss details of linked lists, queues, stacks, and related data structures - it's expected that students will read this material from the textbook (since this material should be known to all students))

  3. (9/20/05)
    • Priority queues
    • Using priority queues to implement sorting (n times EnQueue + n times DeQueue)
    • Definition of a heap and its basic properties
      • Efficient implementations of basic operations:
        • EnQueue (insert a new element in the heap) can be performed in O(log n) time
        • DeQueue (removing the largest element from the heap) can be performed in O(log n) time
        • MaxFind - one can find the largest element in O(1) time
      • Using an array to implement a heap
        • Elegant, fast, and space-efficient implementation
        • O(n)-time algorithm for building a heap for any set of n elements
    • HeapSort - an optimal sorting algorithm that uses a heap and sorts n numbers in time O(n log(n)).
    • Trees, binary trees and their properties
    • Traversing a tree: recursive algorithms to compute height, depth, and size of all nodes
    • Suggested reading: Chapter 2 in the textbook

  4. (9/27/05)
    • Detailed discussion of Homework Assignment 1. Solutions to all problems were presented and discussed in details.
    • Finding minimum element in a set of n numbers.
      • Natural algorithm runs in O(n) time and performs n-1 comparisons.
      • Formal proof that every algorithm requires at least n-1 comparisons.
    • Extensions of the minimum finding algorithm:
      • Finding the smallest and the largest element in a set of n numbers
        • can be done with 1.5 n - 3 comparisons! (using a "tournament tree" approach)
      • Finding the smallest and the second smallest element in a set of n numbers
        • can be done with n + log2n - 2 comparisons! (using a "tournament tree" approach)

  5. (10/4/05)
    • Dictionary
    • Maintaining a dictionary using sorted arrays
    • Maintaining a dictionary using the look-up table (bucket arrays)
      • Perfect performance but huge space usage
    • Hashing
      • Definition
      • Collision handling schemes
      • Choice of good hash functions
    • Binary search trees
      • Basic implementation
      • findElement, insert, delete all take O(height(T)) time in the worst-case
      • Sorting using binary search tree
        • Once we have a binary search tree, an inorder numbering of the nodes will give the sorted order of the elements
        • Since (as we will prove later) sorting n numbers requires W(n log(n)) time, building a binary search tree requires W(n log(n)) time as well
    • AVL-trees
      • Definition
      • Key property: AVL-tree with n nodes has height not greater than 2 log2n + 2
    • Suggested reading: Chapters 2.5, 3.1, and 3.2 in the textbook

  6. (10/11/05)
    • AVL-trees: examples
    • 2-4 trees and red-black trees
    • B-trees
    • Sorting: Merge-sort and Quick-sort
    • Merge-sort: an efficient sorting algorithm using divide-and-conquer approach
    • Quick-sort: "quick" (but on average only) sorting algorithm using divide-and-conquer approach
    • Suggested reading: Chapters 3.2, 3.3, 4.1 and 4.3 in the textbook

  7. (10/18/05)
    • Detailed discussion on problems from Homework 2
    • Bucket sort and radic sort.
    • Discussion on the topics to be covered on the midterm.
    • Suggested reading: Chapter 4 in the textbook

  8. (10/25/05)
    • Midterm Exam. It was open textbooks. There were 5 questions (all of the same worth) and students time until 8:45pm to solve them (so, 2 hours and 45 minutes). The exam covered all material discussed so far.

  9. (11/1/05)
    • Detailed discussion about problems from Midterm and discussion on grading policies.
    • Lower bound for (comparison-based) sorting.
    • Suggested reading: Chapter 4.4 in the textbook

  10. (11/8/05)
    • Long discussion about problems from Programming Assignment 1.
    • Brief recap of the lower for comparison-based sorting (Chapter 4.4 in the textbook).
    • Analysis of average running time of Quick-Sort (Chapter 4.3.1 in the textbook).
    • Selection problem:
      • Sorting gives a trivial algorithm for selection running in time O(n log n).
      • By using priority queues (heaps) we can solve selection in time O(n + k log n).
      • A modification of Quick-Sort (called Quick-Select in the textbook) solves the selection problem in O(n2) worst-case running time, and in O(n) average-case running time.
      • Brief discussion on a (worst-case) linear-time algorithm for selection.
    • Data structures for union-find.
    • Suggested reading: Chapter 4.2, 4.3.1, 4.4, 4.7, Exercise C-4.24 in the textbook

  11. (11/15/05)
    • (Yet again a) long discussion about problems from Programming Assignment 1.
    • Data structures for union-find.
    • Divide-and-conquer technique for problem solving.
    • Faster (than naive) algorithm for integer multiplications
      • Naive (school) algorithm for multiplying two n-bits numbers requires O(n2) operations.
      • A divide-and-conquer scheme leads to an algorithm that multiplies two n-bit numbers in time O(nlog23) = O(n1.585).
    • Master theorem: a generic approach for solving basic recurrences
      • Solves many recurrences in the generic form T(n) = a T(n/b) + f(n)
    • Strassen's algorithm for fast matrix multiplication
      • Standard (school) algorithm for multiplying two n x n matrices requires O(n3) operations.
      • A clever divide-and-conquer scheme leads to an algorithm that multiplies two n x n matrices in time O(nlog27) = O(n2.808).
    • Greedy approach for problem solving.
    • The fractional knapsack problem: a greedy algorithm finds an optimal solution in O(n log n) time.
    • Basic task scheduling problem: a greedy algorithm finds an optimal solution in O(n log n) time.
    • Suggested reading: Chapter 4.2, 5.1, and 5.2 in the textbook

  12. (11/22/05)
    • Greedy algorithms: basic task scheduling problem: a greedy algorithm finds an optimal solution in O(n log n) time.
    • Dynamic programming: improving running time of bruto-force recursive/backtracking algorithms by memorizing partial solutions.
    • Matrix chain product: efficient computing of product of matrices using dynamic programming.
    • 0-1 knapsack problem: efficient solution using dynamic programming.
    • Suggested reading: Chapters 5.1 and 5.3 in the textbook

  13. (11/29/05)
    • Detailed discussion about problems from Homework 3.
    • Graphs, and their applications.
    • What are graphs: definitions of undirected graphs, directed graphs, weighted graphs.
    • Graph representations:
      • Adjacency matrix and adjacency lists.
    • Depth-first search algorithm.
    • Breadth-first search algorithm.
    • Suggested reading (necessary): Chapters 6.1, 6.2 and 6.3.1 in the textbook

  14. (12/6/05) Last day of classes
    • Using breadth-first search to find shorted path from a source node to every other node (in unweighted graph)
    • Topologocal sorting (O(n+m)-time algorithm).
    • Minimum spanning tree problem.
    • Kruskal algorithm for the minimum spanning tree problem (running time O(n + m log(n))).
    • Prim's algorithm for the minimum spanning tree problem (running time O((n + m) log(n))).
    • Shortest path problems in (weighted) graphs.
    • Bellman-Ford algorithm for the single-source shorthest path problem (running time O(nm)).
    • Dijkstra algorithm for the single-source shorthest path problem for graphs with non-negative weights (running time O((n+m) log (n)).
    • Using "matrix multiplications" to find all-pairs shortest paths in a graph (running time O(n3 log(n))).
    • Suggested reading (strongly advised): all material covered in the class that can be found in the textbook.

Final Exam took place on Tuesday, December 20, 6:00-9:00pm in KUPF 117.

  • It was open textbooks.
  • There were 5 questions (all of the same value) and students had time until 9:00pm to solve them (so, 3 hours).
  • The exam covered all material discussed in the class and from the textbbok.
  • The final exam is worth 35% of the total score!

No grades for the final exam will be posted here. The final grades for the course will be posted directly to the registrar on around Tuesday/Friday, December 22/23. After that date, every student can always ask the instructor per email (czumaj@cis.njit.edu) about her/his performance on the final and individual scores for every problem.

Artur Czumaj