605.620.81 - Algorithms for Bioinformatics

Course Structure

The course materials are divided into seven two week modules. The Modules can be accessed by clicking Modules on the left menu. A module will have several sections including the overview, content, readings, discussions, and assignments. Students are encouraged to preview all sections of the module before starting. All modules run for a period of fourteen (14) days. Students should regularly check the Calendar and Announcements for assignment due dates.

Course Topics

Topics include

• advanced data structures(red-black and 2-3-4 trees, union-find),
• algorithm analysis and computational complexity (recurrence relations, big-O notation, introduction to NP-completeness, Approximation Algorithms),
• sorting and searching,
• design paradigms (divide and conquer, greedy heuristic, dynamic programming), and
• graph algorithms (depth-first and breadth-first search, minimum spanning trees,).

Advanced topics are selected from among the following: Multithreaded Algorithms, Matrix Operations, Linear Programming, String Matching, Machine Learning Algorithms, FFT, and Parallel Algorithms.

Course Goals

To become conversant with the strategies and techniques driving the cost of an algorithm, describing and applying them  appropriately.

Course Learning Outcomes (CLOs)

• Analyze algorithms to determine correctness relative to functional requirements.
• Analyze algorithms to determine worst-case complexity in terms of time and space requirements.
• Design algorithms to meet functional requirements, matching appropriate strategies to problems.
• Design algorithms to meet target complexity bounds in terms of time and space complexity.
• Implement algorithms to assess their actual performance compared to expectations from analysis.
• Identify and apply theoretical concepts of algorithm design to real world applications.

Textbooks

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to algorithms (4th ed.). Cambridge, MD: The MIT Press.
ISBN-13 ‏ : ‎ 978-0262046305
Web site for book: http://mitpress.mit.edu/algorithms/

Other Materials & Online Resources

Textbook information for this course is available online through ep.jhu.edu/bookstore.
Additionally, the following references or their later editions may be useful for this course, if you find yourself struggling with specific skills:
• Horowitz, S., Sahni, S., & Rajasekaran, S. (1997). Computer algorithms in C++. New York: Computer Science Press.
• Horowitz, S., Sahni, S. & Mehta, D. (1995). Fundamentals of data structures in C++. New York: Computer Science Press.
• Sedgewick, R. (1998). Algorithms in C++ parts 1-4. (3rd ed.). Reading, MA: Addison-Wesley.
• Sedgewick, R. (2002). Algorithms in C++ part 5. (3rd ed.). Boston, MA: Addison-Wesley.
• Carrano, F. M. & Prichard, J. (2002). Data abstraction and problem solving with C++: Walls and mirrors, 3/E. Boston, MA: Addison-Wesley.
• Langsam, Y., Augenstein, M. J., Tenenbaum, A. M. (1996). Data structures using C and C++. (2nd ed.). Englewood Cliffs, N.J. : Prentice Hall.
• Standish, T. A. (1997). Data structures in java. Reading, MA: Addison-Wesley.
• Weiss, M. A. (1999). Data structures and problem solving using java. Reading, MA: Addison-Wesley.
• Epp, S. S. (2011). Discrete mathematics with applications. (4th ed.). Pacific Grove, CA: Brooks/Cole. • Johnsonbaugh, R. (1990). Discrete mathematics. (2nd ed.). New York: Macmillan.
• Ross, K. A, & Wright, C. R. B. (2003). Discrete mathematics. (5th ed.). Upper Saddle River, N.J.: Prentice Hall.

Required Software

You will need the following software:
• Java SE 8 or 11 (JDK 1.8 or 1.11) available from http://www.oracle.com/technetwork/java/javase/downloads/index.html
• An (optional) IDE on your computer to facilitate developing programming assignments. The following are freeware IDEs you may wish to try:

Student Coursework Requirements

It is expected that each module will take approximately 18 – 24 hours per module to complete, keeping in mind that each module is two weeks. Some students may find they need additional time. Here is an approximate breakdown: reading the assigned sections of the texts (approximately 2-6 hours) as well as some outside reading, watching the lecture videos (approximately 2-4 hours), collaborative problem (2-4 hours of direct interaction, plus additional individual preparation), practice homework (approximately 2-4 hours), written homework (approximately 2-5 hours). Additional time will be required for the programming assignments. The instructors recommend that most students take this course by itself due to the time commitment.

This course will consist of six student requirements:

1. Self-Check Quiz Questions (5% of Final Grade Calculation) (computer graded - direct questions to Eleanor)
For each module, there is a quiz using the Test and Quizzes tool. Students are required to complete each quiz during the associated module. The quizzes themselves are not part of the grade, but credit for each one is earned when completed during the associated module. Quiz completion credit is 5% of the final grade calculation.

2. Chapter Presentation (15% of Final Grade Calculation)(Eleanor and Sidney)
During the last module, Module 7, students will work in groups of four, on a presentation of one of the chapters in the Applications section of the text. The exact number and size of groups will depend on class size. Selections will be made from Chapter 26 Parallel Algorithms, Chapter 28 Matrix Operations, Chapter 29 Linear Programming, Chapter 30 Polynomials and the FFT, Chapter 32 String Matching, and Chapter 33 Machine Learning Algorithms. Chapters 27, and 31 may be added if needed. Selections will be on a first come, first serve basis on the last day of module 6. It is recommended students preview the chapters before the module starts. Student groups will use VoiceThread to record their presentation. For help with the tool see the VoiceThread Guide page located in Course Information section on the left menu. The presentation is due on Saturday midnight of the second week of the module and must be submitted to the course website. During the final three days of the second week of the module, each student will review and comment on the other presentations. Each student will turn in a score sheet describing the division of labor within their group and evaluating their group. A rubric will be provided.

3. Collaborative Problems (3) (20% of Final Grade Calculation)(Eleanor)
During three of the first six modules, students will be divided into collaboration groups of three to five students to work on a collaborative problem in a group discussion forum. The problems will be selected from the more conceptually difficult aspects of the material and will give students an opportunity to interactively grapple with the concept. The groups will be changed for each problem. Students will be graded on the level and quality of their participation, along with the correctness and completeness of the group solution. A rubric will be provided. The collaboration will be open with the module but needs to be started by the second Wednesday of the module and will run through the second Monday of the module. Collaborations are supported via the discussion forums and others tools found in each group. Suggestions on using the Pages tool can be found under Syllabus and Course Information in the left menu.

4. Homework (Michael)
There will be regular, assigned written, homework and practice homework. The number of assigned problems will vary each week since the usefulness of written homework varies with the course content. The required textbook has problems after each section of the text as well as problems at the end of each chapter. Problem 5.2-3 is problem number three after section 5.2 of the text. Problem 25-2 is the second problem at the end of Chapter 25. Homework problem sets are numbered to generally correspond with the module. In writing up your homework and practice homework, please keep in mind the following:

• The burden of communication is on you. If we do not understand what you mean then we cannot give you proper credit. This means that you should include explanations of your thought process within reason, draw diagrams where appropriate, make it easy for us to follow what you are doing and clearly identify your intended answer.
• Use proper grammar and spelling. Type your responses where possible. Please use a scanner to upload any handwritten material. Photographs taken with your phone will not be accepted.
• Algorithms should be written in structured English or pseudo-code, not in Java or C++. Homework is not intended to be executed even if it asks for code. Regardless of what the book specifies - write pseudo code, not JAVA. Make sure appropriate detail is included.
• Do not try to sit down on Sunday night and do all the homework that is due that week. You need to have time to think about the problems.

a. Practice Homework (constituting 10% of Final Grade Calculation)
Practice homework is due on midnight of the second Wednesday of the module and must be submitted to the course website. There is an automatic two days of grace for Practice Homework, otherwise LATE Practice Homework will not be accepted, except by prior arrangement with the instructor, and only under unusual circumstances. Problems are selected to emphasize aspects of the lecture material, to cover points omitted in lecture and to prepare students regular homework. It is in your own best interest to do the practice homework. It is important to attempt all the homework problems, even if you are not able to complete them all, it will still be beneficial and will help you with other components of the course. In writing up your homework, please keep in mind the following:

      The point of the scoring system is to encourage you to do the problems, so full points will be awarded as long as a reasonable, in-depth, and sincere effort is made on each problem. Practice Homework will be scored as follows:
      • 2 points - a reasonable, in-depth and sincere effort (only trivial errors permitted)
      • 1 points - a sincere effort but lacks depth and may have errors
      • 0 points – no effort or a minimal and insincere, effort

b. Homework Assignments (constituting 20% of Final Grade Calculation)
Written homework is due on Tuesday midnight of the second week of the module and must be submitted to the course website. Homework has an automatic two days of grace. After that, LATE Written Homework will not be accepted, except by prior arrangement with the instructor, and only under unusual circumstances. Homework will typically, but not always, be one or two problems per chapter. Problems are selected to emphasize the difficult concepts of the lecture material. Scores will be based on correctness and completeness of the solution provided. Well thought out, efficient, correct answers are generally worth more points than correct answers which are mundane and less efficient. Both of these are worth more points than correct, efficient answers generated by an attributed, literature search. The value is in working through the problem yourself. These problems are selected to be comparable to the kind of problems that might be selected for a take home exam. They are each worth around 10 points. The points for each problem may vary a little depending on the difficulty of the problem.

5. Programming Projects (30% of Final Grade Calculation: 10% each) (Sidney and Michael)
There will be three programming projects worth 10% each of the total grade. All programming assignments will consist of JAVA programs coded and executed by the student. The use of JAVA is required. The projects are strictly individual work. There is no collaboration on the project.

Programming assignments One and Three are due on midnight of the second Tuesday midnight of the specified module. Programming Assignment Two is due on the first Tuesday of Module 5. All programming assignments must be submitted to the course website. Assignments received after midnight of the specified deadline are considered late and the grade will be reduced by 5 points. The grade will be reduced by an additional 5 points for each subsequent day that the assignment is late. Programming Assignments more than 1 week late cannot be accepted, except by prior arrangement with the instructor. It is your responsibility to get your programming assignments in on time. Problems with your system do not constitute a legitimate excuse for late assignments, so make plans to deal with the unavailability of your system. All programs are to be turned in electronically. Programs which do not produce some form of legitimate output cannot be accepted for grading.

If you are disappointed in your programming assignment score on either programming assignments one and two, with a grade below 75%, you may fix and resubmit it before Module 7. Submissions after that must be arranged on a case by case basis with the instructor. Fixes will only be accepted on issues of correctness, modularity, error checking, output presentation, and use of named files. Fixes will not be accepted on documentation, input sets, or the Analysis.

Fixes are subject to a 25% penalty in fairness to those with a correct original submission, e.g. if you fix something which had a 20 point deduction you will only get back 15 points. Please see the Programming Assignments Guidelines located in the Programming Resources section of the course website for additional policies on the programming assignments and how they will be graded.

Grading Policy

Half of the course grade is based on participation and just putting forth a reasonable amount of effort in completing the work. Anyone should be able to pass this course but you need to do well on the written homework and the programming assignments to do well in the course.

Final grades will be determined by the following weighting:

Item	Note	Weight (%-age)
Self-check quizzes	Quizzes must be completed during the module to earn credit.	5%
Chapter Presentations	Module 7	15%
Collaborative Problems	Three group problems in Modules 1, 3, 6	20%
Practice Homeworks (6)	One set per module	10%
Homeworks (6)	One set per module	20%
Programming Assignments (3)	These are equally weighted:  10% each	30%

We will use the following +/- grading system:

Score Range	Letter Grade
100-98	= A+
98-94	= A
94-90	= A−
90-88	= B+
88-84	= B
84-80	= B−
80-78	= C+
78-74	= C
74-70	= C−
70-60	= D
<60	= F

Course Policies

Programming Language

This is a computer Science course and the official language of the EP computer Science program is Java. You are expected to be a competent Java Programmer already. If this is not the case, please speak to the instructor immediately.

Due Dates

A note about due dates: All times are specified in terms of EST/EDT, local to the instructors. Discussion postings, homework, and programming assignments are always due at midnight on the specified day. Although submissions after the deadline will be accepted, they will be marked late. We generally will not quibble over a couple of minute’s lateness. Multiple submissions will also be accepted, so if you think of something you forgot to do, a new answer for a question, or if we ask you to redo something, just go ahead and resubmit to Canvas in the same place as the first submission. There is a three hour grace period on the deadline for the Presentations, Collaborative Problems, and Programming Assignments.  There is no grace period on the Quizzes or the Discussion.. The grace period for Homework and Practice Homework is 2 days. After the relevant grace period ends, LATE work will not be accepted, except by prior arrangement.


Module Learning Guide

This is a general learning guide for all the modules except the last one. The last module will be presentations and will have a separate learning guide. It is intended to help you stay on top of the course in an organized manner, and to serve as a checklist each week. Each module of the course runs for two weeks, from Wednesday through the second Tuesday. We will also start the course with a module of introduction (referred to as module zero) that runs concurrently with the first part of Module 1, followed by twelve weeks containing course content.

The standard learning guide for each module is:

• Wednesday – Friday: Start new material. Begin the module by viewing the Introduction video if there is one.
• Continue by skimming the assigned chapters of the textbook.
• Review the Practice Homework assignment, to see if you need to ask clarification questions.
• Wednesday - Attend Office Hours at 9 pm. Get clarification on Homework, lab, or content.
• Thursday - End of grace period on Homework of previous module.
  
• Thursday to Saturday - Start viewing lecture videos. Start the practice problems.
• Go back to read the relevant chapters in depth.
• Start working on the programming assignment if there is one.
• Friday -Use the posted solution, available after Thursday midnight, to figure out what you did wrong on the homework of the last module and try to correct it.
• Please post any questions to the appropriate Discussion forum. Take notes throughout the week for questions you may need to ask during Office hours.
• Sunday – Office Hours at 8 pm. Get clarification on Homework, lab, or content.
• Monday - Start coordinating with your group on the collaborative problem if there is one.
• Wednesday - Finish and submit the Practice problems due.
• Wednesday - Start working seriously on collaborative n assignment for the module if there is one.
• Wednesday - Office Hours at 9pm. Get clarification on Homework, lab, or content.
• Please post any questions to the appropriate Discussion forum. Take notes throughout the week for questions you may need to ask during Office hours.
• Review the Vocabulary list for this module and make sure you know the terms and their meanings.
• Thursday to Saturday - Continue with collaborative assignment and written homework.
• Friday - End of grace period on Practice Homework
• Saturday - Practice problem solutions released. Use the solution to figure out what you did wrong on the practice homework and try to correct it.
• Complete the quiz or quizzes if you have not yet done so.
• Sunday - Work on written homework. Office Hours at 8 pm. Get clarification on Homework, lab, or content.
• Monday - Finalize and submit collaborative assignment if there is one.
• Tuesday - Complete this module by submitting the written homework by midnight. Peer reviews or programming project due, as applicable.

Plagiarism

Plagiarism is defined as taking the words, ideas or thoughts of another and representing them as one's own. If you use the ideas of another, provide a complete citation in the source work; if you use the words of another, present the words in the correct quotation notation (indentation or enclosed in quotation marks, as appropriate) and include a complete citation to the source. See the course text for examples.

Students should read policies pertaining to academic misconduct and netiquette at http://ep.jhu.edu/genpolguid. Students will be asked to take an Honor Pledge. You are expected to do your own work and turn in your own work. Help from other sources must be acknowledged. It is okay to discuss problems with others for perspective or to make sure you understand it correctly, but the code you write must be your own. Downloading code from other sources for the programming assignments, while strongly discouraged, should absolutely be properly attributed. Downloading code from other sources for the programming assignments, while strongly discouraged, should absolutely be properly attributed. In case it is not clear, paying someone to write original code to submit under your name is plagiarism.

Students found to have committed plagiarism will earn a grade of zero on the plagiarized assessment e.g. plagiarizing a homework problem will result in a zero on the entire homework assignment. Subsequent incidents will result the student failing the course. Subsequent violations will result in an F for the course. Students committing plagiarism will be referred to the Associate Dean. Contact us if you have any questions, no matter how slight, about this policy, or if you have questions about a particular assignment.

In addition, we would like to point out that our textbook is widely used and the solutions to many of the homework problems are available on the internet. While you might possibly get away with submitting a published solution, it is in your own best interest to try to work out the problems on your own. If you get it wrong, you can then learn from the solutions published on the website. That way you will still be properly prepared for work later in the course. Also, of course, there is no way to determine if a solution on the web is correct or not.

All submissions will be vetted through the anti plagiarism software, TurnItIn. In addition to checking for similarity to work previously submitted by others in this course, this school, or other locations, it can now check for AI generated content. Submitting AI generated content is considered plagiarism, in case it is not already clear to you.

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.