605.621.87 - Foundations of Algorithms

Expanded Course Description

Algorithms are unambiguous abstract, programming language independent, specifications for performing calculation, data processing, automated reasoning, and other tasks.   They are at the core of most technologies used in modern computation systems.  All software-based systems implement algorithms of some sort.  The total system performance of these systems relies just as much on choosing efficient algorithms as the hardware, especially as problem data set sizes increases.  Studying algorithms helps to develop widely applicable analytical skills not just to solve individual problems but to develop efficent “recipes” for getting answers to many problems that extends beyond software systems and are relevant to all sciences and fields of human endeavor.

Students often find this course very demanding.   Successful students with a very strong background in discrete mathematics and data structures may expect to spend an average of 15 to 20 hours/week on the readings, homework and discussion boards.  The design/programming/analysis projects take additional time.

Course Structure

This is self paced, but synchronized course.

The course materials are divided into modules.  Modules are released weekly.  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.

There are weekly reading assignments with biweekly homework assignments.  The biweekly homework assignments consist of a combination of both individual and collaborative problems.  Additionally there are three design/programming/analysis assignments.  The design/programming/analysis assignments are an individual effort. 

A major focus of this class is developing your algortithm research, design and analysis skills.  Weekly module and group discussions are a critical element of this learning process, and student participation and interaction is important.   Students are expected to actively engage in all weekly module discussions and collaborative homework assignment discussions.    Discussion groups are randomly assigned, and change biweekly to enable students to interact with all other students in the course.    There are fixed deadlines on the week, e.g., discussions due by Thursday 11:59pm, replies by Sat 11:59pm, homework Mon 11:59pm. Each week, the class moves onto a new module.

Each week you must start a thread in the open discussion forum associated with the current module. This first post must be done by Day 3 of the week where the module is presented. Your fellow group members need to reply in your thread within two days of the initial posting (i.e., by Day 5), and you will reply to theirs. You will be graded on your initial post and the replies to your group members for your on-line contributions. There is a degree of subjectivity, but I am looking for the relevance of your observations/comments to the topic in hand and the extent to which you have researched your responses.

Homework assignments will include one or more collaborative problems. Each group (which is the same as your discussion groups) will work together to solve the collaborative problems. Collaboration may take place within a Canvas discussion forum created by the group. External collaborative discussions e.g., email, telephone, Zoom, IRC, Teams etc. are permitted.  At the end of each homework assignment, you will submit a performance assessment of how your group members contributed to the collaborative problems assigned. These evaluations are due when the homework is due. Failure to submit timely evaluations will also negatively impact your participation score.

Course Topics

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:

Course Goals

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.  Some modules, such as those pertaining to NP-Complete problems and their approximations, touch upon deep mathematical concepts. These topics can be intimidating to approach, but diligence will be rewarded with insights into fascinating areas of analysis.  By the end of the course, you’ll be able to:

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.
• Explore synergies between data structures and algorithm design.
• Implement algorithms to assess their actual performance compared to expectations from theoretical analysis.

Textbooks

The required textbook (also referred to as CLRS, from the first initial of the author's last names) for this class is:

Introduction to Algorithms, 4th Edition

Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
Publisher: The MIT Press; 4th edition (April 5, 2022)
ISBN-10: 026204630X
ISBN-13: 978-0262046305

This is perhaps the most well known introductory textbook to algorithms. It is a language-independent presentation of the core ideas behind algorithms and algorithm complexity with an equal focus between theory and analysis.   The language independence allows concentration on the theoretical concepts without requiring knowledge of a specific programming language.  It is also an excellent reference once you complete the course, since each chapter is relatively self-contained and presents an algorithm or a design technique that can be quickly implemented using any imperative programming language. 

The following text is entirely optional for this class.  It is NOT required, and there will be NO assigned readings from it.  You may, however, that it very helpful as it provides a highly readable and well-organized summary to proof writing and analysis. It is also a good review of critical elements of logic, set theory, cardinality, and topology- all key elements of discrete mathematics associated with algorithm design.

Transition to Proof: An Introduction to Advanced Mathematics

Author: Neil R. Nicholson
Publisher: Chapman and Hall/CRC: 1st edition, April 2, 2019
ISBN-10: 0367201577
ISBN-13: 978-0367201579


Both are available online thru the JHU library.

Required Software

This section will use Python as the mandatory programming languages and ECLIPSE as the preferred development environment.  Eclipse is a free and open-source software and can be downloaded from the ECLIPSE Foundation website (https://www.eclipse.org/downloads).   Python is available at the Python Foundation website (https://www.python.org/).

Student Coursework Requirements

Homework 40%
There will be 7 Homework Assignments. Most homework assignments will include one or more collaborative problems. Each group (which is the same as your discussion groups) will work together to solve the collaborative problems. Collaboration may take place within a Canvas discussion forum created by the group.  External collaborative discussions e.g., email, telephone, Zoom, IRC, Teams are permitted. These collaborative group discussions will not be monitored by the instructor. At the end of each homework assignment, you will submit a performance assessment of how your group members contributed to the collaborative problems assigned. These evaluations are due when the homework is due. Failure to submit timely evaluations will also negatively impact your score. Your collaborative grade reflects (a) how well you performed on the group problem according to your peers; (b) how well you assessed your peers with specific and actionable information.

Programming/Analysis Assignments 40%
There will be 3 Programming & Analysis Assignments. The Programming and Analysis assignments are not collaborative.  

Class Discussion 20%
You will be put into a small group of students whose membership will change every two modules so that you will have the opportunity to interact with all the members of the class. Each week you must start a thread in the open discussion forum associated with the current module. This first post must be done by Day 3 of the week where the module is presented. Your fellow group members need to reply in your thread within two days of the initial posting (i.e., by Day 5), and you will reply to theirs. You will be graded on your initial post and the replies to your group members for your on-line contributions. There is a degree of subjectivity, but I am looking for the relevance of your observations/comments to the topic in hand and the extent to which you have researched your responses.

Grading Policy

Grades will follow the following scale:

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.