605.621.86 - 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
Instructor
Steven Leon
Course Structure
The course materials are divided into modules which can be accessed by clicking Course Modules on the left 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 Calendar and Announcements for assignment due dates. Here is are some key dates coming up:
- Thursday 1/25 (Day 3 of Module 1) 11:59pm PST: Create your own thread under Module 1 Discussion forum, for example, titled as Group - Name - .
- Saturday 1/27 (Day 5 of Module 1) 11:59pm PST: Reply to all of your group members' threads under Module 1 Discussion forum.
- Thursday 2/1 (Day 3 of Module 2) 11:59pm PST: Create your own thread under Module 2 Discussion forum, for example, titled as Group - Name - .
- Saturday 2/3 (Day 5 of Module 2) 11:59pm PST: Reply to all of your group members' threads under Module 2 Discussion forum.
- Monday 2/5 (Day 7 of Module 2) 11:59pm PST: Participate in HW1 Discussions with your group under Group - HW1 Discussions forum. Someone in the group can start with initiating threads by collaborative problems and subproblems in HW 1. In each HW1 group discussion area, there should be 4 threads created so that everyone assigned to the group can participate, assuming there are 4 group members.
Course Topics
- Introduction - Analyzing/designing algorithms, asymptotic notation
- Basic Analysis - Summations, solving recurrences
- Randomized Algorithms - Probability, randomization
- Sorting - Heapsort, Quicksort, sorting in linear time
- Data Structures - Order statistics, binary search trees
- Optimization - Dynamic programming, linear programming
- Aggregate Analysis
- NP Completeness - Proofs and famous NP-Complete problems
- Graph Algorithms
- Approximation Algorithms
Course Goals
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? Understanding how to categorize the difficulty of computational problems and their solutions (i.e., this course) will provide you with a foundation to handle a broad spectrum of cross-disciplinary problems.
Emphasis will be placed on developing 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)
- Understand, recognize, analyze and implement common algorithm design techniques, including use cases and tradeoffs.
- Analyze and determine algorithm run time complexities in order to choose among different algorithm designs.
- Understand and apply common techniques for logically proving the correctness of an algorithm.
- Implement and apply standard data structures such as linked lists and binary search trees to design efficient algorithms.
Textbooks
Required
Cormen, T. H. (2022). Introduction to Algorithms (4th ed.). Cambridge, MA: MIT Press.
ISBN-10: 026204630X
ISBN-13: 978-0262046305
Textbook information for this course is available online through the appropriate bookstore website: For online courses, search the BNC Virtual website.
Required Software
Please complete assignments using Python as a programming language. Please visit Programming Assignment Guidelines under Syllabus & Course Information for further details. Other programming languages are accepted on a case-by-case basis. Please check with me prior to using another language.
Student Coursework Requirements
It is expected that each module will take approximately 7–10 hours per week to complete. Here is an approximate breakdown: reading the assigned sections of the texts (approximately 3–4 hours per week) as well as some outside reading, listening to the audio annotated slide presentations (approximately 2–3 hours per week), and writing assignments (approximately 2–3 hours per week).
Timeliness is critical. This course format works only as long as everyone keeps up as a group. Therefore, we take timeliness seriously.
For any assignment/post/discussion, 10% points will be deducted from your grade per day (example: 3 days late = 70% deduction). This includes all discussions, homeworks, programming assignments, everything. Make sure that as well as posting by the due date, you are responding to the posts submitted by your peers in your designated group (by Saturday night at midnight). For every group member you do not respond to, points will be deducted. If you have posted late for the Module Discussions or have not responded to your peers, this will be reflected in your grade.
That said, we are not monsters. If you have a problem, communicate as soon as you know it. Either email the instructor, your group mates, whoever is affected.
This course will consist of the following basic student requirements:
Discussion, Participation, and Collaboration (25% of Final Grade Calculation)
You are responsible for carefully reading all assigned material and being prepared for discussion. The majority of readings are from the course text. Additional reading may be assigned to supplement text readings.
Post your initial response to the discussion questions by the evening of day 3 for that module week. Posting a response to the discussion question is part one of your grade for module discussions (i.e., Timeliness).
Part two of your grade for module discussion is your interaction (i.e., responding to classmate postings with thoughtful responses) with at least two classmates (i.e., Critical Thinking). Just posting your response to a discussion question is not sufficient; we want you to interact with your classmates. Be detailed in your postings and in your responses to your classmates' postings. Feel free to agree or disagree with your classmates. Please ensure that your postings are civil and constructive.
I will monitor module discussions and will respond to some of the discussions as discussions are posted. In some instances, I will summarize the overall discussions and post the summary for the module.
Evaluation of preparation and participation is based on contribution to discussions. The 25% of the Discussion, Participation and Collaboration Grade is divided into the following:
Weekly Module Discussions (12.5% of Final Grade Calculation) Each week you’ll be required to post a thread to the open discussion forum associated with the weekly module. This should be done by Day 3 of the week the module is posted. You’ll also need to post responses in the same open discussion forum within two days of the initial postings (i.e., by Day 5). I’ll evaluate you on timeliness in posting to the module discussion as well as your ability to provide clarifying responses to the discussion.
Collaborative Problems (12.5% of Final Grade Calculation) In addition to weekly discussions, each homework assignment will include one or more collaborative problems and small groups will be assigned at the beginning of each homework problem set. Each group will be required to work together to solve the collaborative problems in a private discussion forum. Avoid using other media for collaborative discussion...they can’t be tracked for grading!
Participation in forums (collaborative homework problems or the weekly module discussion) will be graded in this manner:
| Post on Time? | Substantive Responses | Grade (max 100) |
| No | 0 | 0 |
| Yes | 0 | 50 |
| No | 1-2 | 50 |
| Yes | 1-2 | 75 |
| Yes | 3+ | 100 |
Based on the above, note that four-five total posts are required for full credit (one post to create a new thread, and three-four responses to others). Posts will be reviewed for substance and timeliness, and that responses should favor threads that currently don’t have responses if reasonable. Avoid:
- A number of posts within a very short time-frame, especially immediately prior to the posting deadline.
- Posts that complement another post, and then consist of a summary of that post.
Homework Assignments (49% of Final Grade Calculation)
Assignments will include a mix of quantitative problem sets, and algorithm design and evaluation problems. All written assignments are expected to be typed in a word processor, the preferred submission type is PDF allowing for ease of grading. Include a cover sheet or heading with your name and assignment identifier. Also include your name and a page number indicator (i.e., page x of y) on each page of your submissions.
Each problem should have the problem statement, assumptions, computations, and conclusions/discussion delineated. All Figures and Tables should be captioned and labeled appropriately.
When using equations, make use of the built-in equation editor for these tools. Try to avoid scanning hand-drawn figures, if needed please ensure they are readable. The grader will make the determination of "readability". If the assignments are not legible, they will be returned to the student with a grade of zero. Be sure each assignment includes a daytime phone number in case the instructor or grader needs to reach you.
Each algorithm you design must be defined in pseudocode consistent with the Pseudocode Restrictions found on the Syllabus & Course Information page.
You are permitted to use Internet resources while solving problems, however complete references must be provided. Please follow the Sheridan Libraries' citation guidance at Citing Other Things - HOW DO YOU CITE AN INTERVIEW, A TWEET, OR A PUBLIC WEB PAGE? and continue to the APA Academic Writer Sample References. Additional example citations are provided at the Purdue University, Purdue Online Writing Lab (OWL), College of Liberal Arts Reference List: Electronic Sources. You can also use training provided by Victoria University Library, Melbourne Australia on Harvard Referencing: Internet/websites.
All assignments are due according to the dates in the Calendar.
If, after submitting a written assignment you are not satisfied with the grade received, you are encouraged to redo the assignment and resubmit it. If the resubmission results in a better grade, that grade will be substituted for the previous grade.
Programming Assignments (26% of Final Grade Calculation)
Each algorithm you designed must be defined in pseudocode consistent with the Pseudocode Restrictions. Your entire submission must follow the Programming Assignment Guidelines.
Pseudocode Restrictions and Programming Assignment Guidelines are items on the Syllabus & Course Information page.
Grading Policy
Type | Grade Percentage |
Homework/Programming Assignments | 75% |
Class Discussion/Collaboration | 25% |
Please see the handout on assignments for guidance on submissions. Grades will follow the following grading scale:
| Grade Average | Letter Grade |
| 100-98 | A+ |
| 97-94 | A |
| 93-90 | A- |
| 89-87 | B+ |
| 86-83 | B |
| 82-80 | B- |
| 79-70 | C |
| <70 | F |
If you are 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.
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.