This follow-on course to data structures (e.g., EN.605.202 Data Structures) 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, introduction to NP-completeness), 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, computational geometry, and approximation algorithms. Students will form groups to work on difficult problems and also to present an advanced topic at the end of the term. The course will draw on applications from Bioinformatics. Prerequisite(s): EN.605.202 Data Structures or equivalent, and EN.605.201 Introduction to Programming Using Java or EN.605.206 Introduction to Programming in Python or equivalent. EN.605.203 Discrete Mathematics or equivalent is recommended. Course Note(s): This course does not satisfy the foundation course requirement for Computer Science, Data Science, or Cybersecurity. Students can only earn credit for one of EN.605.620, EN.605.621, EN.685.621 or EN.705.621
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.
Topics include
To become conversant with the strategies and techniques driving the cost of an algorithm, describing and applying them appropriately.
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/
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.
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:
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.
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% |
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 |
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:
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.