605.421 - Foundations of Algorithms Course Homepage
Instructor Information
John Sheppard
Email: john.sheppard@cs.montana.eduWork Phone: (406) 994-4835
Dr. Sheppard received his BS in computer science from Southern Methodist University in 1983. Later, while a full-time member of industry, he received an MS in computer science in the Johns Hopkins Part Time Engineering program (1989). He then continued his studies and received his Ph.D. in computer science from Johns Hopkins in the day school (1996). Dr. Sheppard is the RightNow Technologies Distinguished Professor in the Computer Science Department at Montana State University and an Associate Research Professor in the Computer Science Department at Johns Hopkins. His research interests include model-based and Bayesian reasoning, reinforcement learning and games, and fault diagnosis/prognosis of complex systems. In 2007, he was elected as a Fellow of the IEEE "for contributions to system-level diagnosis and prognosis." Prior to joining the full time faculty at Hopkins, Dr. Sheppard was a member of industry for 20 years. His prior position was as a research fellow at ARINC. Dr. Sheppard became a member of the EPP faculty in 1994. He teaches courses in algorithms, artificial intelligence, machine learning, and evolutionary computation.
Course Information
Course Description
This follow-on course to data structures (e.g., 605.202) provides a survey of computer algorithms, examines fundamental techniques in algorithm design and analysis, and develops problem-solving skills required in all programs of study involving computer science. Topics include advanced data structures (red-black and 2-3-4 trees, union-find), recursion and mathematical induction, algorithm analysis and computational complexity (recurrence relations, big-O notation, NP-completeness), sorting and searching, design paradigms (divide and conquer, greedy heuristic, dynamic programming, amortized analysis), and graph algorithms (depth-first and breadth-first search, connectivity, minimum spanning trees, network flow). Advanced topics are selected from among the following: randomized algorithms, information retrieval, string and pattern matching, and computational geometry.
Prerequisites
605.202 Data Structures or equivalent.
Course Goal
To provide the fundamental background and experience in the design and analysis of computer algorithms in preparation for more advanced study in computer science.
Course Objectives
- Understand the workings of several algorithms applicable to a variety of problem types.
- Develop the ability to assess the advantages and disadvantages of different types of algorithms.
- Understand methods for designing time and space efficient algorithms.
- Develop the ability to evaluate the performance of algorithms in terms of worst case and average case time and space requirements.
When This Course is Typically Offered
This course is offered every semester at various EPP locations. The specific section taught by Dr. Sheppard is typically offered online during the Fall semester.
Syllabus
Topics Covered
- Introduction to Algorithms
- Analysis Techniques
- Data Structures Review
- Advanced Data Structures
- Probability and Amortized Analysis
- Sorting Algorithms
- Search and Selection Algorithms
- Graph Algorithms
- Network Flow Algorithms
- Dynamic Programming
- String Processing
- Computational Geometry
- NP Completeness
- Randomized Algorithms
Student Assessment Criteria
| Weekly Homework Sets | 50% |
| Four Programming Assignments | 30% |
| Class Participation | 20% |
In terms of assigning a final letter grade, the following is provided as guidance. Note that grading does not following strict percentages. You may consider them as a worst-case scenario (i.e., 90%+ for A, 75-89% for B, 60-74% for C); however, it is common for the scale to be adjusted downward based on relative performance of the class. The goal is for the top 20% of the students to receive an A and the remainder of the class a B. The lowest homework grade (except the last) and the lowest program grade (except the last) will be dropped.
Computer and Technical Requirements
Proficiency in at least one structured or object-oriented programming language (e.g., Java or C++) and proficiency in data structures.
Participation Expectations
All work is to be through individual effort. Occassional collaborative problems are also assigned. The computer science academic integrity code is followed and enforced strictly. The class participation grade is based on attendance, in-class discussion, and Sakai use.
Textbooks
Textbook information for this course is available online through the MBS Direct Virtual Bookstore.
Course Notes
There are notes for this course.
Final Words from the Instructor
This course uses Sakai to provide the principal course content and tools (including online office hours) for the student. Sakai can be accessed at http://sakai.jhu.edu.
Term Specific Course Website
(Last Modified: 08-17-2009 at 9:41:30 PM)