Lectures: TTh 12:30 - 1:45, Room 309 BH
Office Hours: I will be in my office (1216 SEO)
Tuesday and Thursday from 9:30 - 11:30. And, running to
lunch between 11:30-12:30. You are welcome to see me anytime
I am in, and if you cannot make those hours, feel free to email me
about another time.
and Analysis of Algorithms by Anany Levitin, Addison
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.
Teaching Assistants: The teaching assistants will
grade your homework assignments under my guidance and with my
instructions. If you have a question or complaint about a
grade, and you are not able to resolve it with the TA, please see
me for help.
The teaching assistants this semester are:
Exams: There will be two midterms (20% each) and one
final examination (35%). The first exam will be September
26. Future exam dates will be announced. The
final will be ???.
Assignments: Homework assignments are worth 25% of your grade. You may do homework with a partner (max 2 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. Read my academic integrity guidelines before you hand in any programs.
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.
Special Dates: The three Thursdays September 5, 19, and 26 are Jewish holidays. I will not lecture these days but I will have a substitute, exam, or announce other plans for these days in class.
|assignment 1||assignment 2||assignment_3||assignment 4|
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.
Reading (3rd Edition)
|1-2||Introduction: Polynomial Time Algorithms versus
NP-Complete Problems. Worst Case and Average
Case Time Complexity Analysis. Simple
Algorithms: Max, Min, GCD, Fast-Exponentiation.
||Chapters 1, 2, 3.4
|3-4||Data Structure Review: Stacks, Queues, Priority
Queues, Height Balanced Search Trees, Heaps. Searching
and Sorting: Bubble Sort, Insertion Sort, Selection Sort,
Heapsort, Quicksort, Counting Sort, Bucket Sort, Radix Sort.
||Chapters 1.4, 3.1, 3.2, 4.1,.4.5 5.1, 5.2, 6.4, 7.1, 11.1,
|First Midterm Exam
|5-6||Graph Algorithms: Topological Sorting, Depth First
Search and Applications, Breadth First Search.
||Chapters 3.5, 4.2|
|7||Graph Algorithms: Shortest Path, Minimum Spanning
Tree, the Union-Find Data Structure, and Amortized Analysis.
|8||Geometric Algorithms: Line Intersection, Convex
||Chapters 3.3, 5.5
||Dynamic Programming: Fibonacci Numbers, Binomial
Coefficients, All Pairs Shortest Path, Knapsack,
Matrix-chain Multiplication, Optimal Triangulation, Fixed
Size Graph Bandwidth. Connection to Queues.
||Second Midterm Exam
|12||Greedy Methods: Huffman Codes, Minimum Spanning Tree
Revisited, Task Scheduling.
||Chapter 9.4, 12.3
|13-14||NP-Complete Problems and Reductions: 3SAT, Vertex Cover,
Hamiltonian Path/Crircuit, Partition, Clique, Independent
Set, Not-All-Equal3SAT, Dominating Set.
Approximation Algorithms: Vertex cover, Traveling salesman problem (TSP), Applet for TSP Approximation.
|Chapters 3.4, 6.6, 11.3
|15||Other topics if time allows: Mathematical
Algorithms, or String Matching: Knuth Morris Pratt
(KMP), and Boyer-Moore, Applet
||Chapters 5.4, 6.5