CS 4122/5122 - Algorithms and Data Structures (Spring 2023)

Advanced computer programming requires an understanding of both the objects on which programs work, the data structures, and the sequences of steps driving the programs themselves, the algorithms. In order for data structures and algorithms to be generally useful, they often must overcome memory and speed limitations of the underlying machine. Thus it is important for the programmer to be able to analyze algorithms for their efficiency in execution and use of space for data.

This course will improve your skills as a programmer by (1) teaching you the mathematical language for talking about program behavior, (2) develop your skills for algorithmic thinking, and (3) sharpen your abilities for data and procedural abstraction.

Below is a tentative schedule for the semester.

This course addresses UMD campus student learning outcomes (SLOs), as well as CS education outcomes specified by the UMD Department of Computer Science and aligned with the standards put forth by the ABET accrediting board.

• SLO 1: Demonstrate competence in a major field
  • The students will gain knowledge of the core methods of

advanced data structures such as use of appropriate data structures and algorithms, and their running times.

• The students will demonstrate competent use of data structures and algorithms in lab and homework assignments.
• The students will demonstrate knowledge of data structures and algorithms on exam questions.

• SLO 3: Think critically and creatively in seeking solutions to practical and theoretical problems.
  • The students will be able to recognize different types of

algorithmic problems and identify the best approach of how to solve them

• The students will be able to determine the most appropriate data structures to utilize, or be able to design their own

There will be weekly assignments which will consist of both programming and non-programming problems. Programming assignments will be based on algorithms written in a generic pseudo-code presented in lecture and in the text. Solutions to programming assignments will be written in C++ without using STL.

All assignments must be submitted by their stated due date.

If you are a graduate student enrolled in 5122, there will be an extra research project. You will need to complete the following steps.

• Select a research paper on a particular algorithm. The paper must be approved by the instructor by the first midterm exam.
• Submit a short report (5-8) pages outlining the paper by the second midterm exam.
• Give a short (10-15 minute) oral presentation about the paper at the end of the semester

This is an upper division course, and therefore I will not make attendance mandatory. However, classroom participation will be graded and included as part of the assignment component for the computation of the final grades.

You can earn participation points by contributing to classroom discussions, answering questions, coming to office hours, etc. To allow a fair chance for everyone to participate, I will sometimes draw names at random to ask questions about the material. Don't worry about getting the answer right! Research suggests that answering questions incorrectly can be valuable for moving information from working memory into long-term memory.

There will be two midterm exams, worth 100 points each and a final exam worth 200 points.

Both exams are closed book, and the final exam will be comprehensive. Exams will not be given early, and makeups must be justified by dire circumstances described to the instructor before the time of the exam. It is Department of Computer Science policy not to return final exams, however they are kept and you can look at your exam in the instructor's office. The UMD Final Examination Policy web page explains the UMD policy about having more than two final exams on a single day, among other things.

Final grades are based on total points distributed approximately as follows:

1. Assignments and participation (approx. 200 points)
2. Midterm Exams (200 points)
3. Final Exam (200 points)
4. Graduate research project (5122 students only) (100 points)

Grades are assigned based on a percentage of the total points.

• The A- cutoff is 90%
• The B- cutoff is 80%
• The C- cutoff is 70%
• The D cutoff is 60%
• Below 60% is an F

Appropriate classroom conduct promotes an environment of academic achievement and integrity. Disruptive classroom behavior that substantially or repeatedly interrupts either the instructor's ability to teach, or student learning, is prohibited. Students are expected to adhere to the Board of Regents Policy.

Academic dishonesty tarnishes UMD’s reputation and discredits the accomplishments of students. Academic dishonesty is regarded as a serious offense by all members of the academic community.

Taking notes is a means of recording information but more importantly of personally absorbing and integrating the educational experience. However, broadly disseminating class notes beyond the classroom community or accepting compensation for taking and distributing classroom notes undermines instructor interests in their intellectual work product while not substantially furthering instructor and student interests in effective learning.

Students are expected to attend all scheduled class meetings. It is the responsibility of students to plan their schedules to avoid excessive conflict with course requirements. However, there are legitimate circumstances that lead to excused student absence from the classroom. These are subpoenas, jury duty, military duty, religious observances, illness, bereavement, and NCAA varsity intercollegiate athletics.

All 1xxx-5xxx courses offered for undergraduate credit should include a final graded component or end of term evaluation that assesses the level of student achievement of one or more course objectives. All final graded components are to be administered or due at the time and place according to the final exam schedule and not during the last week of class.

UMD is committed to providing a positive, safe, and inclusive place for all who study and work here. Instructors and students have mutual responsibility to ensure that the environment in all of these settings supports teaching and learning, is respectful of the rights and freedoms of all members, and promotes a civil and open exchange of ideas.

Sexual harassment means unwelcome sexual advances, requests for sexual favors, and/or other verbal or physical conduct of a sexual nature. Such conduct has the purpose or effect of unreasonably interfering with an individual's work or academic performance or creating an intimidating, hostile, or offensive working or academic environment in any University activity or program. Such behavior is not acceptable in the University setting. See also: Board of Regents Policy.

The University provides equal access to and opportunity in its programs and facilities, without regard to race, color, creed, religion, national origin, gender, age, marital status, disability, public assistance status, veteran status, sexual orientation, gender identity, or gender expression. Equal Opportunity and Affirmative Action and the Office of Student Conduct & Conflict Resolution are both available to all UMD employees, students, and participants in University-related activities to discuss issues or concerns regarding University policies or practices involving potential bias, discrimination, harassment or retaliation that an individual may have experienced or observed.

Thoughtful dialog is a cornerstone of higher education. This expectation is upheld in the University of Minnesota's Board of Regents Policy: Academic Freedom and Responsibility, which says in part:

SECTION II. ACADEMIC FREEDOM. Academic freedom is the freedom, without institutional discipline or restraint, to discuss all relevant matters in the classroom, to explore all avenues of scholarship, research, and creative expression, and to speak or write on matters of public concern as well as on matters related to professional duties and the functioning of the University.