Instructor: Joseph JaJa
Assignments:
- Assignment #1: 2.2-2, 2.3-5, 2.3-7, 2-1, 3.1-4, 3.2-4. Due September 7. Solution
- Assignment #2: 4.2-5, 4-1, 5.2-1, 5.2-4, 5.2-5, 5.3-4. Due September 14. Solution
- Assignment #3: 10.2-7, 10.3-4, 10.4-6, 11.2-1, 11.2-4, 11-1, 11-2 (parts a,b,c only). Due September 21. Solution
- Assignment #4: 12.2-7, 12.3-3, 6.4-2, 6-1, 7-1. Solution in Class on September 26.
- Assignment #5: 7.1, 8.3-3, 8.4-2, 8-3. Due: October 12. Solution
- Assignment #6: 15-2, 15-3, 16.1-3, 16.2-2. Due: October 24. Solution
- Assignment #7: 22.1-7, 22.2-5, 22.3-4, 22.3-11, 22.4-3, 22-3. Due: October 31. Solution
- Assignment #8: 23.1-6, 23.2-7, 34.1-3, 24.3-4, 24.4-10. Solution in Class on November 7.
- Assignment #9: 24.1-3, 24.3-4, 24.4-10, 24-1, 25.1-10, 25-1. Due: November 30. Solution
- Assignment #10: 26.1-6, 26.1-7, 26.2-9, 26-4. Due: December 7. Solution
Course Objectives: Mathematical modeling, analysis, and proof techniques related to computer algorithms and systems. Probability, combinatorics, and graph theory as they pertain to the design and performance of computer systems. Techniques for the design and analysis of algorithms and data structures. Study of efficient algorithms from areas such as graph theory and networks. Understanding of the inherent complexity of problems: polynomial time, NP-completeness, and approximation algorithms. The course emphasizes mathematical rigor.
Prerequisite topics: Properties of functions and basic combinatorial principles, relations, equivalence classes, partial orders and related topics, asymptotics and recurrences, elementary sorting algorithms, programming experience, and basic calculus.
Textbook: Introduction to Algorithms, T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, McGraw-Hill, Second Edition, 2001 (required).
Core Topics:
1. Introduction (Chapters 1-5)
Asymptotic Analysis of Algorithms
Recurrences and Summations
Counting and Probability
Some basic techniques for estimating the complexity of algorithms
2. Elementary Data Structures (Chapters 10-12)
Stacks, queues, and linked lists
Hashing techniques
Binary Search Trees
3. Overview of Elementary Sorting Algorithms (Chapters 6-8)
Heapsort and priority queues
Quicksort and randomized algorithms
Linear time sorting algorithms
4. Advanced Algorithmic Methodologies (Chapters 15-16)
Dynamic programming and some related applications
Greedy algorithms and related applications
5. Basic Graph Algorithms (Chapters 22-26)
Basic graph exploration techniques
Minimum Spanning Trees
Single-source shortest paths
All-pairs shortest paths
Network Flow
6. NP-completeness (Chapter 34)
Basic framework: polynomial time and reducibility
NP-completeness: basic notion and proof techniques
Some NP-complete problems
7. Linear Programming (Chapter 29)
Basic Concepts
The Simplex Algorithm
Duality
Applications to Graph Optimization Problems
8. Advanced Data Structures (Chapters 13-14, 21)
Red-Black trees
Interval trees
Data structures for disjoint sets
9. Computational Geometry (Chapter 33)
Interval trees and related applications
Convex Hull
Closest Pair
Course Grade: Homework (20%); Midterms (25% each); and Final (30%).
Late Assignments: No late assignments will be accepted but assignment with lowest score will not be counted.
Midterm I: Thursday, September 28; Midterm II: November 2; Final: Tuesday, December 19, 4-6.
Office Hours: Tu, Th 3-4:30 or by appointment
Contact Information: joseph@umiacs.umd.edu; 301-405-1925.
The University of Maryland, College Park has a nationally recognized Code of Academic Integrity, administered by the Student Honor Council. This Code sets standards for academic integrity at Maryland for all undergraduate and graduate students. As a student you are responsible for upholding these standards for this course. It is very important for you to be aware of the consequences of cheating, fabrication, facilitation, and plagiarism. For more information on the Code of Academic Integrity or the Student Honor Council, please visit http://www.studenthonorcouncil.umd.edu/whatis.html .