# CS 2123 Data Structures and Algorithms Course Syllabus

*Fall 2017, TTh 2pm-3:15pm, Keplinger Hall 3010 (aka U2)*

Course Website: https://secon.utulsa.edu/cs2123/

Piazza Course Discussion: https://piazza.com/utulsa/fall2016/cs2123/home

## Instructor Information

Dr. Tyler Moore https://tylermoore.utulsa.edu

*Email:* tyler-moore@utulsa.edu. Please send course-related inquiries
as private messages to me via Piazza. This helps me keep track of
course communications.

*Office:* Rayzor Hall Rm. 2140

*Office Hours:* Mondays 10:30-11:30am, Tuesdays 10:30-11:30am, and by appointment

*Email Hours:* I strive to respond to course-related emails within 24 hours on weekdays. Inevitably I may overlook some messages; if more than 24 hours has passed, feel free to send me a reminder.

TAs: Tom Wu and Michael Sun

The TAs support the class by offering scheduled drop-in hours to help answer any questions you have, particularly those related to programming projects. They can also help with questions related to the course material. While you can alway come see me during office hours, in most cases your first stop should be to see the TAs, particularly if you have a question outside the time for my office hours. TAs also can answer questions posted to Piazza.

## Course Description

Concepts of data structures including B trees, AVL trees, and hashing. Introduction to algorithm design and analysis, with emphasis on using appropriate data structures. Algorithmic techniques discussed include induction, greedy, divide and conquer, and dynamic programming. Algorithms are presented for canonical problems and students will implement several using Python.

### Prerequisites

CS 2003

### Learning Outcomes

Upon completing this course, students should be able to:

- apply canonical algorithms for a range of applications
- implement algorithms from written description or pseudocode using Python
- characterize the efficiency of algorithms using mathematical notation and by measuring execution empirically
- select the appropriate data structure to efficiently implement algorithms
- outline informal arguments assessing an algorithm's correctness
- reduce real-world problem specifications to subproblems that can be solved using the appropriate algorithmic technique

### Topics

- Algorithm efficiency analysis
- Induction, recursion, and recurrence relations
- Graph traversal and topological sorting
- Balanced binary search trees (B trees, AVL trees)
- Greedy algorithms, including interval scheduling, shortest paths in weighted graphs, and Huffman codes
- Divide and conquer algorithms, including mergesort, counting inversions, closest pair and skyline
- Hashing data structures
- Dynamic programming algorithms, including weigthed interval scheduling, knapsack, and edit distance
- Intractability, including reductions and problem spaces (P, NP)

## Textbook

Algorithm Design. Jon Kleinberg and Eva Tardos. Addison Wesley, 2005. ISBN 0-321-29535-8

## Course Calendar

See the online schedule for up-to-date details and reading assignments.

## Coursework

### Homework

There are 5 assignments, each equally weighted:

- Algorithm analysis and induction
- Graph traversal and tree data structures
- Greedy algorithms
- Divide-and-conquer algorithms and hashing
- Dynamic programming

Each assignment will include a combination of written responses and Python programming. Students are strongly encouraged (but not required) to work in pairs on assignments. Students working in pairs should submit a single assignment for both students. Students working in pairs may not split the problems; instead, students are expected to work jointly on each problem in the assignments, including coding. Students may not work with the same partner on consecutive assignments.

Turn in a hard copy of the assignment, along with a printout of code and requested outputs. Students must also submit an electronic copy of the code to Harvey.

### Exams

There are two midterm exams and a comprehensive final exam. The exams will include written problems; the exams may also require hand-written pseudo-code or Python code. Exams will be closed-book, closed-notes and closed-Internet unless otherwise announced.

## Piazza

https://piazza.com/utulsa/fall2016/cs2123/home

Piazza is an online Q&A system designed by computer scientists to encourage better course feedback and support. To facilitate collaboration and quick responses to your questions, you are encouraged to post questions to Piazza, as well as answer your classmates' questions on Piazza.

All online course-related correspondence should take place on Piazza. When you have a question, consider whether it should be addressed only to the instructor, or if can be shared with your classmates. As a guide, most questions about homework assignment could be shared with your classmates, as many could have the same question. Private correspondence, such as information about when you are sick, personal circumstances, etc., should be sent via private message on Piazza. I may not respond to your emails, but I will respond to private messages sent via Piazza.

## Grading Policies

### Grade Distribution

- Homework (30%)
- Midterm 1 (20%)
- Midterm 2 (20%)
- Final Exam (25%)
- Participation (5%)

I use standard percentage cut-offs when determining letter grades (e.g., [90-100] is an A, [80-90) is a B, etc.). I do not use a curve in assigning grades, as I believe grading on a curve discourages collaboration among students. Occasionally, though, a particular assignment may be too difficult and so I reserve the right to adjust the score appropriately.

In order to reward progress in learning that occurs over the course of the semester, I will let students replace their lowest score on an assignment with their score on the final exam, provided that the final exam grade is higher than the lowest-graded assignment. For example, suppose you make an 82%, 88%, 90%, 91% and 95% on the homework assignments and receive an 89% on the final exam. The 82% assignment grade is replaced by 89%, and the final exam is also treated as 89%.

### Attendance and Participation Policy

I expect you to attend classes and participate in class discussions. I understand that occasionally circumstances may arise so that you must miss class. This is OK, but I would appreciate if you send me a private message on Piazza in advance letting me know that you won't be able to attend class. Chronically missing class is not acceptable, and I reserve the right to withdraw students from the course in the event of persistent absence.

I also expect that you will keep up with the reading. This means that you should have completed the reading listed on the schedule *before* the corresponding lecture.

The participation grade (5%) is based upon a combination of recorded attendance and my assessment of your participation in class. I encourage active participation, and so I look favorably when students ask questions and attempt to answer questions raised during lecture. I look unfavorably on activities that demonstrate disengagement from the lecture, such as sleeping, browsing the web during class, etc.

### Policy on Late Work

The range of topics covered in this class is substantial, and course material often builds on concepts introduced in prior assignments and exams. Consequently, it is essential that you do not fall too far behind. As a result, assignments really are due at the time stated in the course schedule. If you have not finished the assignment before it is due, please turn in what you have completed.

There are three exceptions to this policy. First, if you have an emergency (e.g., serious illness, death in the family), please let me know as soon as possible so we can work out an accommodation.

Second, students are given 4 lateness coupons for assignments (but not
exams) for use throughout the semester, with one coupon equal to a
24-hour extension. To redeem a lateness coupon, you must send a Piazza private message with subject "CS 2123 Lateness Coupon" **BEFORE**
the assignment is due. In the body of the post please let me know how
many coupons you wish to redeem.

The third exception to the strict deadline policy is for unforeseen circumstances that affect everyone: the power goes out on campus two hours before an assignment is due, for example. In this case, I will extend the deadline in a reasonable manner (e.g., extend by 24 hours after power is restored). I will post an announcement to Piazza if such a circumstance arises.

### Collaboration and Attribution

I encourage collaboration between students on assignments and when
studying. Collaboration is an essential skill for engineering, not to
mention life in general. Unless I say otherwise, feel free to discuss
assignments with your classmates, including ideas for
how to solve problems. **Please do not, however, share code,
equations, or written answers that solve an assignment directly with
other students**. Solutions to homeworks should be written from
scratch and must not be pieced together from other students.

**If you work with another student on assignments, you must turn in a single copy with both students' names.**

It is also important to give credit to others when appropriate. If you implement an idea that you got from another student (or students), please say so. Furthermore, if you consult a web resource that directly assists you, please say so. As a reminder, it is also not acceptable to copy code or equations directly from a web resource that solves a problem on an assignment.

### ENS College Academic Misconduct Policy

In keeping with the intellectual ideals, standards for community, and educational mission of the University, students are expected to adhere to all academic policies. Cheating on examinations, plagiarism, and other forms of academic dishonesty violate both individual honor and the life of the community, and may subject students to penalties including failing grades, dismissal, and other disciplinary actions. For full details please see the College of Engineering and Natural Sciences Academic Misconduct Policy.

Any student found to have committed academic misconduct activities will, in the first instance,
receive a grade of 0 on the assignment or exam. In the second instance, the student will receive a failing grade for the course. **Note that this includes copying code or writing from the Internet or other resources without attribution.** Note that University policy requires me to notify the Associate Dean for Academic Affairs in the event of identifying academic misconduct.

### Rules and Conduct for Using Computers

The following rules govern the proper use of computers and related resources at the University of Tulsa. Violation of such rules constitutes academic misconduct. Penalties may range from reduction of course grade to dismissal from the university.

- The computer or account allocated to you is to be used only by you and only for assigned course work. Logging in, running jobs under, accessing or using information in computers or accounts other than those assigned to you constitutes academic misconduct and is strictly prohibited.
- Giving your account number or account information such as passwords to anyone else constitutes academic misconduct and is strictly prohibited. Giving the keyless entry code to any room to anyone else constitutes academic misconduct and is strictly prohibited.
- Programs and data supplied by an instructor for use in courses remain the property of the instructor and/or the University of Tulsa. They may not be copied without express consent of the owner.
- Reading, copying, modifying or deleting of files created by other people is not allowed. Note that programs turned in that are "identical" in syntax or semantics will not be accepted, and the students involved may fail the course or even be dismissed from the University. This is a serious matter.

### Extra Credit

It is my policy to not offer extra credit assignments on a per-student basis. To ensure fairness, extra credit may only be offered to all students, and would most likely take the form of a modest reward for attending an optional lecture, not an extra assignment.

## Special Needs

### Disability Accommodations

Students needing academic accommodations for a disability must first be registered with the Center for Student Academic Support to verify the disability and to establish eligibility for accommodations. Students may call 918-631-2315, email csas@utulsa.edu, or visit http://utulsa.edu/campus-life/student-academic-support/contact/ to begin the process. Once registered, students should then schedule an appointment with the professor to make appropriate arrangements.

### Religious Observance

Religiously observant students wishing to be absent on holidays that require missing class should notify their professors in writing at the beginning of the semester, and should discuss with them, in advance, acceptable ways of making up any work missed because of the absence.

## Disclaimer

Please note that this syllabus is subject to change. Any changes to the syllabus will be announced in class, on the course website, and/or on Piazza.