Status: December 22, 2000

Instructor:

Schedule: (only in Fall 2000)

Grading and Policies:

• Grading will be based on 5 problems sets (homeworks), one programming assignment, one quiz, an in-class midterm, and a final.

• Five homeworks will be handled out. Each homework is worth 50 points. One homework with the lowest grade will be dropped from grade consideration. Thus, the homeworks contribute a total of at most 200 points towards the final grade. Homeworks were posted on the course Web-page http://www.cis.njit.edu/~czumaj/TEACHING/CIS435-F00.html both in postscript and in Adobe Acrobat format.
  • Homeworks are due at the start of class on their due date. They can be submitted either per email czumaj@cis.njit.edu or be delivered in a hard-copy at the beginning of the class. Handwritten or typed solutions will be accepted.
  • No later solutions will be taken into consideration!
  • If the homework is to be submitted per email, it must be in one of the following formats: postscript file (preferable), pdf-file (2nd preference), ASCII text, Word format.
  • Solutions must be readable (especially handwritting!!!), concise and complete.
  • Show your work, as partial credit will be given. You will be graded not only for the correctness and efficiency of your answers, but also on your clarity. Be neat.
  • Bonus points will be awarded for answers that are particularly clever, simple, or efficient.
  • Each time you must design an algorithm, try to design it as efficient as possible. The faster algorithm you will describe the better grade you will get.
  • Unless it is stated otherwise, each algorithm described must be provided with a full analysis of its correctness and its running-time.
  • The work you turn in must be your own personal work, composed and written by you. 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 quiz, 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.
  
  
• One programming assignment was handled out. It required implementation of some algorithms or data structures presented in the course. The implementation was to be in C++. There were no grades for the assignment, but they are required to be turn in in order to pass the course. They were prepared to assist you in understanding the material presented in the class.
• One "evaluation" quiz was handled out at the beginning of the course (September 14, 2000). There are no grades for the quiz.
• The midterm exam took place during the class on Tuesday, October 24, 2000. It was closed book/note/etc.
  The midterm exam is worth 150 points.

• The final exam took place on Monday, December 18, 2000, in KUPF 206 from 8:30 am to 11:00 am.
  The final exam was cumulative (that is, all course material were examined) and was open-textbook and open class-notes only.
  The final exam is worth 300 points.
  
  

Homeworks:

1. Problem Set 1 was due (8:30 am) September 21, 2000.
   
   
2. Problem Set 2 was due (8:30 am) October 5, 2000.
   
   
3. Problem Set 3 was due (8:30 am) October 19, 2000.
   
   
4. Problem Set 4 was due (8:30 am) November 21, 2000.
   
   
5. Programming assignment was due December 18, 2000.
   
   
6. Problem Set 5 was due (8:30 am) December 18, 2000.
   
   

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 undergraduate course catalog: The course deals with advanced topics in data structures and algorithm, including mathematical induction, analysis and complexity of algorithms, and algorithms involving sequences, sets, and graphs such as searching, sorting, order statistics, sequence comparisons, graph traversals, etc. Optional topics include geometric, algebraic, and numeric algorithms.

Topics to be covered (tentative):

References in parenthesizes below refer to the chapters in the textbook.

1. General issues: (Ch 1)
   • 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
2. Basic "mathematics":
   • Big-Oh notation (Ch 1-2)
   • solving recurrences (Ch 4)
   • summations (Ch 3)
   • sets, relations, functions (Ch 5)
   • graphs and trees (Ch 5)
3. Sorting and order statistics: (Ch 1, 7-10)
   • the importance of sorting (in practice and in the understanding of the algorithm design)
   • Insertion sort, Selection sort, Merge sort, Quick sort, Heap sort, Radix and Bucket sort (optionally: sorting in external memory)
   • medians and selection
4. Basic data structures: (Ch 11-14, 19, 22)
   • lists, stacks, and queues
   • trees
   • dictionaries
   • priority queues
   • search trees and binary search trees
   • balanced binary search trees (Red-Black trees)
   • (optionally: splay trees and B-trees)
   • hashing
   • data structures for disjoint sets (Ch 22, 24) [not covered]
5. Basic techniques and their applications: [not covered] (Ch 1, 16-18, 24-26)
   • divide-and-conquer
   • dynamic programming
   • greedy algorithms
   • amortize analysis
   For each of the techniques we shall present its applications and, in particular, we shall introduce graph problems here (Ch 23-26).
6. Additional problems: [not covered]
   • string matching (Ch 34)
   • polynomial and matrix multiplication (optionally: Fast Fourier Transform and basic algebraic algorithms) (Ch 31-32)
   • problems that are "hard": NP-completeness and NP-hardness (Ch 36-37)

References:

• MAIN TEXTBOOK:
  T.H. Cormen, C.E. Leiserson, and R.L. Rivest: »Introduction to Algorithms«, The MIT Press/McGraw Hill, 1990