Fundamental Algorithms, Spring 1998

These are materials for the course "Fundamental Algorithms" taught by Jonathan Goodman in the Spring term of 1998 at the Courant Institute of Mathematical Sciences, NYU. The lectures are Wednesday evenings from 7 to 9 pm in room 101 of Warren Weaver Hall, starting January 21. The problem sessions are Mondays from 7 to 8 pm in the same room. My office hours are Mondays 8pm to 9pm (after the problem session) and Tuesdays 4pm to 6pm. If you cannot make these times, please contact me for an appointment. This course is part of the Masters degree program in Computer Science at the Courant Institute

Course description:

Prerequisites: Basic computer science at the undergraduate level. This includes experience with a high level programming (such as Pascal, C, or Java), familiarity with recursion and recursive programming methods, and basic data structures (arrays, pointers, stacks, queues, and trees). Mathematics including exponentials, logarithms, differentiation, and integration. Actually, the course contains review of many of these topics, so it is suitable for people whose analytical skills are rusty.

Purpose: The algorithms, data structures, and analyses discussed in this course are the main tools of the trade for all of computer science. In that sense, this course is the prerequisite for all the rest of computer science.

Material: The course begins with a review of the mathematical foundations of algorithm analysis. This includes the "big O" notation, asymptotic orders of magnitude, recurrence relations, and basic probability (for analyzing average running time). We then describe and analyze the major algorithms for sorting (bubble sort, merge sort, heap sort, quick sort, radix sort, ...). Next comes storage and retrieval strategies, first hashing, then trees. After that, we discuss graphs and graph algorithms (depth first search for connected components, Kruskal's and Prim's algorithms for minimum spanning trees, Dykstra's algorithm for shortest paths, ...). If time permits, I want to touch on parallel computing.

Grading: The course will be graded on the basis of weekly written homework assignments and a final exam. There will be no programming assignments.

Texts: The required course text is Introduction to Algorithms by Thomas Coreman, Charles Leiserson , and Ronald Rivest (called CLR). This book should be available at the NYU bookstore. Students will probably find An inside Guide to Algorithms: Their Application, Adaptation, Design, and Analysis, by Alan Siegel and Richard Cole, (called SC) both in our Computer Science department, a very helpful supplement. These notes (actually, the draft of a book) may be purchased at the Unique Copy Center (252 Greene St., down the block from Warren Weaver Hall, (212)420-9198 ).

Teaching assistants: Ye Sun and Chung Yung. They will grade homeworks and hold office hours. You may contact them by email with questions or comments. They will contact me regarding questions or comments they cannot answer themselves. They may bring something to my attention without telling me who they heard from.

Final exam: Wednesday, May 6, at 7pm in the same room. Actually, I'm not certain about the room, but if it's different, the new room will be posted on the current room door. The exam will last two hours and will cover material from the whole semester. There will be some questions of the difficulty of the homework questions and some easier questions about how the various algorithms work. You can download the final exam (slightly edited from the version I actually gave, in order to fit better on the page and correct some minor errors that were found during the exam). The source consists of a TeX file and a figure that was translated form a .fig file to a .eps file. The postscript file is also available, as is a version translated into HTML.

Lecture topics and suggested readings:

Each week, I will post the topic of the lecture and suggested readings from the two texts that cover the same material. If you are preparing for the Computer Science Department core exam, you should get copies of previous exams and do the questions as the course proceeds. You should be able to do the unstarred exercises in CLR. Note on code fragments: I am using code fragments to illustrate many of the algorithms. They are written in a polyglot computer language that draws on the greatest of the existing computer languages, namely FORTRAN, Pascal, C, and C++. I hope it is clear what they do, even they do not rigorously follow any particular algorithm convention. Please report bugs in these fragments to me. You may argue about programming style if you have standing to do so (e.g. are an expert in software engineering).

For a basic motivation of the subject, read chapter 1 of CLR and/or SC.

• January 21: mathematical background. Recurrence relations, running times, orders of magnitude, estimating sums by integrals, exponentials and logarithms. Read CLR chapters 2, 3, and 4 and/or SC chapter 2. Both of these texts put more emphasis on solving recurrence relations than I think is necessary for the applications we will meet.
• January 26: problem session. We discussed ordering functions and determining which functions grow faster than others. We discussed problems 2.2 and 2.3 on page 38 of CLR.

• January 28: More discussion of recurrence relations. Sorting based on comparison: bubble sort, insertion sort, selection sort, merge sort, heap sort, and (time permitting) quicksort. Read section 1.1, the introduction to sorting and order statistics (p. 137), chapter 7, and possibly chapter 8 of CLR. Similar material is in SC in sections 5.1 and 5.2. Code fragments for the lecture:
• Basic insertion sort
• Insertion sort exchanging records.
• Insertion sort exchanging pointers to records.
• Insertion sort sorting keys.
• Merge sort.
• Check whether an array is in heap order, clumsy top down approach.
• Check whether an array is in heap order, simpler bottom up approach.
• February 2: problem session. We spent most of the time discussing an exmaple algorithm and its work time. We also did a few more comparisons of growth rates of functions involving logs.

• February 4: Priority queues as an abstract data type (ADT) and their application in event driven simulation. The heap data structure and O(log(n)) implementations of delete_min and insert. Using these operations to sort. Heapify and the O(n) buildheap algorithms. Quicksort, randomized pivot choice, best and worst case running time. The recurrence relation for the expected running time using randomized pivot. Read chapters 7 and 8 in CLR and/or SC sections 5.2 and 5.3. Section 5.3 of SC has a very useful discussion of the details of efficient implementations of quicksort. This lecture, I did not use code fragments.

• February 9: Problem session. We went over homework 1.

• February 11: The end of the average case analysis of quicksort. The quickselect algorithm and order statistics. the decision tree analysis of sorting and the proof that O(n log(n) ) binary comparisons are necessary to sort n numbers if only such comparisons are allowed. Beginning of O(n) sorting algorithms: counting sort. What it means for a sorting algorithm to be stable. Radix sort. CLR chapters 9 and 10; SC sections 5.3 to 5.5. There is much more detail in SC than we need.

• February 16: no problem session today because of Presidents' Day.

• February 18: The end of O(n) sorting: bucket sort. Review of linked lists (read CLR, section 11.2). Hashing and associative arrays. Hash tables, hash functions, collision resolution strategies of chaining (open hashing) and open addressing (closed hasnhing). Read CLR chapter 12 and/or SC section 6.8. There is a code fragment illustrating associative arrays

• February 23: Problem session. We went over homework 2.

• February 25: Finishing and starting: Finish sorting algorithms by quickly covering radix sort and bucket sort. Review hashing with a clearer discussion of deleting and rehashing in closed hashing. Begin the discussion of trees. Data structures representing binary and general trees. Binary search trees. Insertion and deletion. Imbalance and its implications.

• March 11: We discuss B trees and the operations on them. We discuss tries. I will hand out an article discussing tries next class. Read CLR , chapter 19. SC does not discuss B trees, but it has a very nice treatment of 2-3 trees, which are similar.

• March 25: All about dynamic programming. The chapter in CLR is quite good and has a number of interesting and clever specific applications. There are two code fragments. One illustrates a recursive evaluation of a hitting probability. The other illustrates the same computation, after it has been ``memoized'' (the term in CLR).

• April 1: Finishing dynamic programming with the longest common sequence algorithm. I apologize again to the class for getting it wrong on March 25. Greedy algorithms, the philosoply (take the best now without regard for the future) and two examples: the scheduling problem and Huffman codes. Some discussion of prefix codes and their decoding using a binary tree (which can be thought of as a trie). This stuff is taken mostly from CLR chapter 17. I made a point of not discussing the abstract matroid theory. My point of view is that it is better to know greedy algorithms as a heuristic with broad applicibility that usually does not give the optimal solution (often far from it) than to know the few special cases where it happens to give the optimal solution. There is a similar treatment in SC section 11.5.

• April 8: The set operations from CLR, chapter 22, see also SC, section 9.5. The first discussion of graphs, their data structures and using set operations to find connected components, CLR, chapter 23 and 24, (we did not cover everything here yet) and SC, chapter 7.

Homework assignments:

I will try to assign a new homework assignment each week. Homework assigned on Wednesday will be ue on Monday, 12 days later, at 7pm. (unless there are NYU holidays in between). Note: this represents a change of policy from what this page originally said. You should download the assignments from this page. You may download the LaTeX source or the postscript suitable for printing on a postscript printer. As a last resort, you can download a version that has been translated into HTML. If you do, you will see that the translator is less than perfect.

Note: I fixed in bug in assignment 2, question 3 on Monday, Feb 9.