Lectures: TR 1:30 - 2:45, Computer Lab - 228 College Center.
Office Hours: TR 11:00 - 12:30 or by appointment.
Text: The Design and Analysis of Algorithms by Anany Levitin, Addison Wesley. Third Edition
Goals: Algorithms is a natural successor to Data Structures, and as such, represents the core of what computer science is all about. Algorithms are fundamental. Every other area of computer science relates in some way to algorithms. An algorithm is a step by step solution to a problem that can be implemented on a computer. Computer architecture motivates parallel algorithms, networks motivate distributed algorithms. Algorithms are used in computer graphics, database theory, AI, compilers, as well as software engineering of all kinds. Theory of computation helps us determine which problems have and do not have efficient algorithms. Sometimes a seemingly small change in the problem affects whether or not there is an efficient algorithm. Surprisingly perhaps, some very important problems have no algorithms at all!
The goal in this class is to understand the fundamental significance of designing and analyzing algorithms in computer science. We study the design of algorithms according to methodology and application. Methodologies include: divide and conquer, dynamic programming, and greedy strategies. Applications involve: sorting, ordering and searching, graph algorithms, geometric algorithms, mathematical (number theory, algebra and linear algebra) algorithms, and string matching algorithms. Analysis of algorithms is studied - worst case, average case, and amortized - with an emphasis on the close connection between the time complexity of an algorithm and the underlying data structures. NP-Completeness theory is examined along with methods of coping with intractability, such as approximation and probabilistic algorithms.
Exams: There will 6 quizzes (25%), the lowest grade will be dropped, and one final examination (35%). The final will be Tuesday, May 6, 12:00, in the lab.
Assignments: Homework assignments are worth 40% of your grade. You may do homework with a partner (max 3 people per group) , as long as you stick with that same partner the whole semester. When you are asked to write, design or describe an algorithm, you may use a computer language or pseudo-code, or a careful English description. When you are asked to write a program or code, you must actually write the program using whatever tool you like.
Grading: You can guarantee an A with 90% a B with 80% etc. I may curve these numbers in your favor, if I feel it is needed.
First week: Read this article about P versus and NP.
Assignment 1 Assignment 2 Assignment 3 Assignment 4
P Versus NP Page A List of NP-Complete Problems
Nice PDF for All Pairs Sh. Path Nice PDF for Closest Pair of Points in 1D and 2D And a Video
My Java DFS Sudoku Solver My Lecture Notes My Video Lectures
Through the prerequisites for this course, you should already know the mathematical material in:
Appendices A and B, Chapter 2, as well as the data structures in Chapter 1, Section 4.
Chapters 1.4, 3.1, 3.2, 4.1,.4.5 5.1, 5.2, 6.4, 7.1, 11.1, 11.2
Graph Algorithms: Topological Sorting, Depth First Search and Applications, Breadth First Search.
Coping with NP-Completeness: Approximation Algorithms: Vertex cover, Traveling salesman problem (TSP), Applet for TSP Approximation.
Randomized Algorithms: Smallest circle encosing 2-dimensional points, PDF paper for DNA solution of Hamiltonian Path by Adelman. Interview with Turing Award winner Adelman. This paper by Adelman is really worth reading.
Chapters 3.4, 6.6, 11.3
15
Other topics if time allows: Greedy Methods: Huffman Codes, Minimum Spanning Tree Revisited, Matroid Intersection, Task Scheduling. Mathematical Algorithms: Extended-Euclid, Fast-Exponentiation, Fast Fourier Transform. String Matching: Knuth Morris Pratt, and Boyer-Moore.
Chapters 5.4, 6, 9.4, 12.3