(Proposed to be MSDS695 Data Structures and Algorithms year 2020)
This course give students a deeper and more general view of data structures and algorithms. While students have examined a number of data structures, such as binary trees, already, this course provides a much more in-depth study. This depth will benefit them greatly in the advanced machine learning course. This course also tends to address many of the difficult algorithm questions students get during job interviews. The critical data structures covered in this class are: lists, linked lists, trees, graphs, hash tables, and tries. The course also covers a variety of common and useful recursive and non-recursive algorithms, such as searching and sorting.
This course is part of the MS in Data Science program at the University of San Francisco.
Here is a great free book on algorithms by Jeff Erickson.
I'll be pulling some material from Kleinberg and Tardos, Algorithm Design. US copyright law allows me to make copies of small portions of books for educational use, which I have done. Please see compressed pdf kleinberg-common-running-times.7z in Canvas course files area. (Do not post that material publicly.)
A very useful set of programming-concepts-for-data-science by former USF MSDS student Shikhar Gupta.
10 Steps to Solving a Programming Problem
By the end of this course, students will be able to:
- Describe object-oriented programming and use objects to construct linked lists, trees, and graph data structures
- Implement critical algorithms, such as searching and list manipulations
- Build hash tables
- Create Trie data structures
- Design recursive algorithms
- Compare algorithmic complexity using “big-O” notation
INSTRUCTOR. Terence Parr. I’m a professor in the computer science and data science departments and was founding director of the MS in Analytics program at USF (which became the MS data science program). Please call me Terence or Professor (the use of “Terry” is a capital offense).
SPATIAL COORDINATES:
- Class is held at 101 Howard in 5th floor classroom 527.
- My office is room 607 @ 101 Howard up on mezzanine
TEMPORAL COORDINATES. Fri Jan 25 - Fri Mar 8, 2019
- Section 01: Fri 10-11:55AM
- Section 02: Fri 2:20-4:15PM
- Exams: Fri 15 Feb before class 9:15am-9:55, Fri Mar 8 in class 10am for both classes at once (different room likely)
INSTRUCTION FORMAT. Class runs for 1:55 hours, 2 days/week. Instructor-student interaction during lecture is encouraged and we'll mix in mini-exercises / labs during class. All programming will be done in the Python 3.6 (not 3.7) programming language, unless otherwise specified.
TARDINESS. Please be on time for class. It is a big distraction if you come in late.
ACADEMIC HONESTY. You must abide by the copyright laws of the United States and academic honesty policies of USF. You may not copy code from other current or previous students. All suspicious activity will be investigated and, if warranted, passed to the Dean of Sciences for action. Copying answers or code from other students or sources during a quiz, exam, or for a project is a violation of the university’s honor code and will be treated as such. Plagiarism consists of copying material from any source and passing off that material as your own original work. Plagiarism is plagiarism: it does not matter if the source being copied is on the Internet, from a book or textbook, or from quizzes or problem sets written up by other students. Giving code or showing code to another student is also considered a violation.
The golden rule: You must never represent another person’s work as your own.
If you ever have questions about what constitutes plagiarism, cheating, or academic dishonesty in my course, please feel free to ask me.
Note: Leaving your laptop unattended is a common means for another student to take your work. It is your responsibility to guard your work. Do not leave your printouts laying around or in the trash. All persons with common code are likely to be considered at fault.
| Artifact | Grade Weight | Due date |
|---|---|---|
| OO hashtable | 10% | Sun, Feb 3 11:59pm |
| Isolation Forest | 40% | Sun, Mar 3 11:59pm |
| Exam 1 | 20% | 9:15AM-9:55AM Fri Feb 15 |
| Exam 2 | 30% | 10AM-11:00AM Fri Mar 8 |
All projects will be graded with the specific input or tests given in the project description, so you understand precisely what is expected of your program. Consequently, projects will be graded in binary fashion: They either work or they do not. The only exception is when your program does not run on the grader's or my machine because of some cross-platform issue. This is typically because a student has hardcoded some file name or directory into their program. In that case, we will take off a minimum of 10% instead of giving you a 0, depending on the severity of the mistake. Please go to github and verify that the website has the proper files for your solution. That is what I will download for testing.
Each project has a hard deadline and only those projects working correctly before the deadline get credit. My grading script pulls from github at the deadline. All projects are due at the start of class on the day indicated, unless otherwise specified.
Grading standards. I consider an A grade to be above and beyond what most students have achieved. A B grade is an average grade for a student or what you could call "competence" in a business setting. A C grade means that you either did not or could not put forth the effort to achieve competence. Below C implies you did very little work or had great difficulty with the class compared to other students.
- Review hash table construction, discuss OO htable project
- Review OO notebook and Operator overloading notebook
- Problem-solving
- Do "quizzes" called Pairs and OO programming on Canvas
- Core data structures
- Introduction to algorithm complexity (“Big-O” notation); see Measuring execution time notebook
- Do complexity practice quiz
- Anomaly detection with isolation forests
- Getting a grip on recursion; see recursion notebook
- Walking data structures; see walking notebook
- Regression tree stumps notebook
- Sorting; see Sorting notebook
- Searching; see Searching notebook
- Graphs; see Graphs notebook
The use of recursive algorithms will be emphasized frequently and wherever appropriate to reinforce this critical mechanism. Discussion of formal algorithm complexity will also be emphasized throughout the lectures.
USF policies and legal declarations
Students with Disabilities
If you are a student with a disability or disabling condition, or if you think you may have a disability, please contact USF Student Disability Services (SDS) for information about accommodations.
Behavioral Expectations
All students are expected to behave in accordance with the Student Conduct Code and other University policies.
Academic Integrity
USF upholds the standards of honesty and integrity from all members of the academic community. All students are expected to know and adhere to the University's Honor Code.
Counseling and Psychological Services (CAPS)
CAPS provides confidential, free counseling to student members of our community.
Confidentiality, Mandatory Reporting, and Sexual Assault
For information and resources regarding sexual misconduct or assault visit the Title IX coordinator or USFs Callisto website.