ADSA

Syllabus of Advanced Data Structures & Algorithms (CS 5130) - Fall 2020

1. Instructor/facilitator

Instructor (facilitator) Contact information
Instructor (Facilitator): Badri Adhikari
Email: adhikarib@edu.umsl
Class meets: Tuesdays 8:20PM - 9:35PM (synchronously via Zoom)
Office hours: By appointment

Teaching philosophy: Computer science and technology is mostly a practical discipline. To learn the fundamentals, an effective strategy is to follow an iterative process of reading, analyzing, and coding. However, many students either like to analyze or code but not both. While some of us enjoy developing the skills for critically assessing the concepts and algorithms, many others enjoy programming and love building things. I think that an effective computer science course should be a balance of (a) theoretical knowledge to understand how computer technology works, and (b) implementation skills to test and execute the theories and algorithms. I design course contents and assignments so that students have an opportunity to improve both: analytical and programming skills. Students with a rich programming experience may find this balance slightly easier but will have a platform to explore further. For many others who do not consider themselves expert programmers, taking such a course will be a rewarding experience.

2. Course description in UMSL catalog

This course covers analysis of time and space complexity of iterative and recursive algorithms, design of data structures for efficient performance, mathematical modeling, dynamic programming, divide and conquer strategies, greedy algorithms, a collection of graph algorithms, linear and integer mathematical programming, and NP-Completeness. [3 credit units].

3. Prerequisites

Graduate Standing in CS

4. Textbook

CLRS 3rd Edition (ISBN 978-0-262-03384-8 or ISBN 978-0-262-53305-8); at amazon.

5. Course topics (Book’s sections)

6. Tentative schedule

Week # Week Classroom topics (tentative)
1 08/25 Syllabus
2 09/01 Discussion of Homework 01 (Chapter 3)
3 09/08 Discussion of Homework 02 (Chapter 15)
4 09/15 Discussion of Homework 03 (Chapter 15)
5 09/22 Discussion of Homework 04 & 05 (Chapter 16)
6 09/29 No meeting
7 10/06 Discussion of Homework 06 (Chapter 17)
8 10/13 Discussion of Homework 07 (Chapter 22)
9 10/20 Mid-term oral test week
10 10/27 Discussion of Homework 08 (Chapter 23)
11 11/03 Discussion of Project ideas
12 11/10 Discussion of Homework 09 (Chapter 24)
13 11/17 Discussion of Homework 09 again (Chapter 24)
14 11/24 Fall break
15 12/01 Project discussion
16 12/08 Discussion of Homework 10
- 12/14 Finals week (oral test)

./lectures-and-homeworks/01-lecture-and-homework.md

7. Academic dishonesty

Any form of academic dishonesty in this class will result in an F for the semester and the case will be referred to the provost’s office for possible further disciplinary action, regardless of how trivial it is. Please don’t use another student’s assignment (or a solution in the internet) to complete your own assignment. Discussing the material is ‘OK’, but please do your work on your own. You should complete the homework alone, not together, and not in a group. If you have any questions about any of the lessons or the assignments, please contact me, and I will point you in the right direction. Please read UMSL’s policy and keep yourself out of plagiarism. Also, please remember that our turnitin tool also automatically checks for plagiarism.

8. Programming language

You are recommended (but not required) to use Python3 for all of your homeworks and project. If you have a reason to use a different programming language (for example if your background is in C++ or Java), please send me an email and I can approve you to use a language of your choice.

9. Due dates and late policy

10. Required one-on-one meeting with the instructor

The mid-term and the final for this course will be in the form of one-on-one interaction with the instructor, via Zoom. Each meeting may be up to 30 minutes long. The meeting will be an opportunity for us to discuss how you are doing in the course. During the meeting we may walk through your homework submissions and explore the aspects of the course that you are struggling with (if there are any). If we find that you are struggling to understand some key concepts and/or unable to complete some assignments, you may be suggested resources so you can do better in the remaining assignments. Please check to make sure that you have submitted all your homeworks and assignments that are due. This will also be an opportunity for you to provide feedbacks. In very rare cases, if I have suspected any plagiarism in your homework submissions, I may also enquire you about it. Closer to the meeting dates, you will be able to sign-up to select a time that works for you during a period of 2/3 days. In order to receive points, you must schedule and attend the one-on-one meetings.

11. Project

In the semester long-project you are expected to demonstrate an implementation of some practical application of algorithms. You are free to work on “any” project related to any of the algorithms we discuss in class. There are no specific requirements. You can be as creative as you want. It is recommended (NOT required) that you prepare your final report using Overleaf. Here is an Overleaf template that you are welcome to use and this is where you can learn more about Overleaf. Here are some example projects by students who took the course in previous semesters.

  1. MAZE-A-TRON game using BFS / project report
  2. Minimum Spanning Tree (Kruskal Algorithm) visualization
  3. Kruskal algorithm visualization

12. Homeworks

There will be some homeworks from each chapter that we cover. Many of the homeworks will require you to implement algorithms. These programming homeworks carry more weights. Some homeworks will require you to trace an algorithm (in paper) and submit your solution. You can take a picture of your solution and submit in Canvas. Please DO NOT submit screenshots of your code, instead, submit the code as a separate .py.txt file. But, you should submit screenshots of your output. If you are using Google Colab to complete your programming homeworks, please convert the notebook to .html files and submit the .html files, for example using htmltopdf.

13. Grade composition

Submission Points
Homeworks 50
Project 10
Mid-term oral one-on-one meeting 10
Final oral exam 30

Note: One (1) bonus point will be assigned to everyone who completes the course evaluation survey. Please email me once you submit the survey.

14. Grading scheme

Points Grade
100% to 94% A
<94% to 90% A-
<90% to 87% B+
<87% to 84% B
<84% to 80% B-
<80% to 77% C+
<77% to 74% C
<74% to 70% C-
<70% to 67% D+
<67% to 64% D
<64% to 61% D-
<61% to 0% F

15. Resources

Your success in this class is important to me. If you need official accommodations, you have a right to have these met. If there are aspects of this course that prevent you from learning or exclude you, please let me know as soon as possible. Together we’ll develop strategies to meet both your needs and the requirements of the course. I encourage you to visit the following links to determine how you could improve your learning as well.