605.621.83 - Foundations of Algorithms
Description
This follow-on course to data structures (e.g., EN.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. Prerequisite(s): EN.605.202 Data Structures or equivalent. EN.605.203 Discrete Mathematics or equivalent is recommended. Course Note(s): The required foundation courses may be taken in any order but must be taken before other courses in the degree. Students can only earn credit for one of EN.605.620, EN.605.621, EN.685.621 or EN.705.621
Expanded Course Description
There are often many ways to solve a computational problem. Can we formalize that some problems are harder than others? Are some problems inherently difficult? How would you determine a "good" solution? Throughout this semester,
you’ll explore topics such as:
- Algorithm asymptotic analysis and big-O notation,
- NP-Complete problems, and their approximate solutions,
- Graph algorithms, dynamic and linear programming, and sorting.
Instructor
Alhassan Yasin
Course Structure
The course materials are divided into modules which can be accessed by clicking Modules on the course menu. A module will have several sections including the overview, content, readings, discussions, and assignments. You are encouraged to preview all sections of the module before starting. Most modules run for a period of seven (7) days, exceptions are noted in the Course Outline. You should regularly check the Grade Center and Announcements for assignment due dates.
This semester, modules are released two at a time. Students are expected to be working in the current module, but students may preview the next week's module and assignments at their option. This is done for the benefit of students who must travel during the semester, or otherwise need to work ahead.
Course Topics
- Basics of asymptotic notation and analysis
- NP-Completeness and problem examples
- Asymptotic analysis of Randomized Algorithms
- Asymptotic analysis of Sorting
- Asymptotic analysis of Data Structures
- Asymptotic analysis of Optimization Problems
- Asymptotic analysis of Advanced Data Structures
- Asymptotic analysis of Graph Algorithms
- Asymptotic analysis of Approximation Algorithms
Course Goals
To develop a broad understanding of the issues associated with designing and analyzing the expected performance of computer algorithms, and to develop greater competence and confidence in applying formal mathematical methods when determining the best approach to solving a computational problem.
Course Learning Outcomes (CLOs)
- Analyze algorithms to determine worst-case complexity in terms of time and space requirements
- Design algorithms to meet functional requirements as well as target complexity bounds in terms of time and space complexity
- Develop data structure techniques for various aspects of programming
- Implement algorithms to assess their actual performance compared to expectations from analysis
Textbooks
Introduction to Algorithms, 3rd Ed., T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, McGraw Hill [ISBN 978-0-262-03384-8].
The textbook is available as an eBook in the Sheridan Library at CLRS eBook.
Other Materials & Online Resources
Programming Language is Python
The programming assignments for this sections are written in Python, distributed as a Jupyter Notebook. Students download the notebook, make modifications to it in a Jupyter environment, then submit the notebook in the assignment portal. One good environment is Google's Colab service online, freely available for use. Another freely available option is the miniconda environment that can be installed on stand-alone computers, and includes an integrated development environment.
If you are new to Python, it's not that hard. The assignments can be done using only the basic features of the language - assignment, math, if/then/else, print, while/for, and built-in data structures like lists, sets, and dicts. Assignments include stub code and function signatures for you to build on, and we can discuss particulars during office hours. We encourage students new to Python to look up tutorials on the web. That said, you are free to implement your assignments in any other reasonable language that you choose (e.g., C++ or Java), but that will make grading and responsiveness more of a challenge for the instructor.
Student Coursework Requirements
| Assignment Type | Grade Percentage |
| Homework Assignments | 49% |
| Programming Assignments | 21% |
| Class/Module Discussion | 15% |
| Collaboration/Homework Discus. | 15% |
Grading Policy
Grades should be interpreted according to these general rubrics:
- A - complete understanding of the topic plus additional insight, creative, or other indicators of advancement beyond complete understanding of the topic;
- B - mastery of the basic material;
- C - attempt to complete the basic material but significant gaps in understanding and mastery exist;
- D/F -failure to complete basic material successfully.
If you’re at risk of receiving a C or lower in the class, at the midpoint of the semester you’ll receive notice from the university or myself.
EP uses a +/- grading system (see “Grading System”, Graduate Programs catalog, p. 10).
| Score Range | Letter Grade |
|---|---|
| 100-98 | = A+ |
| 97-94 | = A |
| 93-90 | = A− |
| 89-87 | = B+ |
| 86-83 | = B |
| 82-80 | = B− |
| 79-77 | = C+ |
| 76-73 | = C |
| 72-70 | = C− |
| 69-67 | = D+ |
| 66-63 | = D |
| <63 | = F |
Course Policies
Academic Integrity Addendum
In addition to the University's academic integrity policies stated elsewhere in this syllabus, Dr. Fink further defines plagiarism as the significant inclusion of related material into your submissions, even if properly cited. For example, if assigned to implement MergeSort, you may not download an implementation from the Internet, revise it, and turn that in. Likewise, you may not import and call out to a pre-made merge sort library, regardless of citation. If you need a snippet that is not central to the assignment, such as code that pretty-prints a list, that is permitted as long as it is properly cited. Further, you must read and honor the policy described in the Assignment Expectations document posted on Blackboard, made available electronically and by request. You must ask Dr. Fink for clarification if you are unsure.
Academic Policies
Deadlines for Adding, Dropping and Withdrawing from Courses
Students may add a course up to one week after the start of the term for that particular course. Students may drop courses according to the drop deadlines outlined in the EP academic calendar (https://ep.jhu.edu/student-services/academic-calendar/). Between the 6th week of the class and prior to the final withdrawal deadline, a student may withdraw from a course with a W on their academic record. A record of the course will remain on the academic record with a W appearing in the grade column to indicate that the student registered and withdrew from the course.
Academic Misconduct Policy
All students are required to read, know, and comply with the Johns Hopkins University Krieger School of Arts and Sciences (KSAS) / Whiting School of Engineering (WSE) Procedures for Handling Allegations of Misconduct by Full-Time and Part-Time Graduate Students.
This policy prohibits academic misconduct, including but not limited to the following: cheating or facilitating cheating; plagiarism; reuse of assignments; unauthorized collaboration; alteration of graded assignments; and unfair competition. Course materials (old assignments, texts, or examinations, etc.) should not be shared unless authorized by the course instructor. Any questions related to this policy should be directed to EP’s academic integrity officer at ep-academic-integrity@jhu.edu.
Students with Disabilities - Accommodations and Accessibility
Johns Hopkins University values diversity and inclusion. We are committed to providing welcoming, equitable, and accessible educational experiences for all students. Students with disabilities (including those with psychological conditions, medical conditions and temporary disabilities) can request accommodations for this course by providing an Accommodation Letter issued by Student Disability Services (SDS). Please request accommodations for this course as early as possible to provide time for effective communication and arrangements.
For further information or to start the process of requesting accommodations, please contact Student Disability Services at Engineering for Professionals, ep-disability-svcs@jhu.edu.
Student Conduct Code
The fundamental purpose of the JHU regulation of student conduct is to promote and to protect the health, safety, welfare, property, and rights of all members of the University community as well as to promote the orderly operation of the University and to safeguard its property and facilities. As members of the University community, students accept certain responsibilities which support the educational mission and create an environment in which all students are afforded the same opportunity to succeed academically.
For a full description of the code please visit the following website: https://studentaffairs.jhu.edu/policies-guidelines/student-code/
Classroom Climate
JHU is committed to creating a classroom environment that values the diversity of experiences and perspectives that all students bring. Everyone has the right to be treated with dignity and respect. Fostering an inclusive climate is important. Research and experience show that students who interact with peers who are different from themselves learn new things and experience tangible educational outcomes. At no time in this learning process should someone be singled out or treated unequally on the basis of any seen or unseen part of their identity.
If you have concerns in this course about harassment, discrimination, or any unequal treatment, or if you seek accommodations or resources, please reach out to the course instructor directly. Reporting will never impact your course grade. You may also share concerns with your program chair, the Assistant Dean for Diversity and Inclusion, or the Office of Institutional Equity. In handling reports, people will protect your privacy as much as possible, but faculty and staff are required to officially report information for some cases (e.g. sexual harassment).
Course Auditing
When a student enrolls in an EP course with “audit” status, the student must reach an understanding with the instructor as to what is required to earn the “audit.” If the student does not meet those expectations, the instructor must notify the EP Registration Team [EP-Registration@exchange.johnshopkins.edu] in order for the student to be retroactively dropped or withdrawn from the course (depending on when the "audit" was requested and in accordance with EP registration deadlines). All lecture content will remain accessible to auditing students, but access to all other course material is left to the discretion of the instructor.