A project based course that looks under the hood at data structures and algorithms to see how they work. In addition to implementing these structures in an application; students will build them from scratch, analyze their complexity, and benchmark their performance to gain an understanding of their tradeoffs and when to use them in practice. Students will write scripts, functions, and library modules to use text processing tools like regular expressions, construct and sample probability distributions to create a Markov language model and gain insight into how grammar works and natural language processing techniques.
Term 3 Course Dates: Wednesday, January 23 – Wednesday, March 6, 2019
Class Times: Monday & Wednesday 3:30–5:20pm
| Class | Date | Topics |
|---|---|---|
| 1 | Wednesday, January 23 | Strings & Random Numbers |
| 2 | Monday, January 28 | Histogram Data Structures |
| 3 | Wednesday, January 30 | Probability & Sampling |
| 4 | Monday, February 4 | Flask Web App Development |
| 5 | Wednesday, February 6 | Application Architecture |
| 6 | Monday, February 11 | Generating Sentences |
| 7 | Wednesday, February 13 | Arrays & Linked Lists |
| 8 | Tuesday, February 19 | Hash Tables |
| 9 | Wednesday, February 20 | Hash Tables Continued |
| 10 | Monday, February 25 | Algorithm Analysis |
| 11 | Wednesday, February 27 | Higher Order Markov Chains |
| 12 | Monday, March 4 | Regular Expressions |
| 13 | Wednesday, March 6 | Written Assessment (Final Exam) |
- Weeks to Completion: 7
- Total Seat Hours: 37.5 hours
- Total Out-of-Class Hours: 75 hours
- Total Hours: 112.5 hours
- Units: 3 units
- Delivery Method: Residential
- Class Sessions: 13 classes, 7 labs
Students must pass the following course and demonstrate mastery of its competencies:
- CS 1.1: Programming Fundamentals
By the end of this course, students will be able to:
- write Python programs that can be run as scripts and imported as modules
- read and write text files stored on disk, manipulate strings, and parse into words
- build web apps with the Flask framework and deploy to the web using Heroku
- construct and sample probability distributions based on observed word frequencies
- create Markov language models and use them to generate new sentences
- write library code organized into separate independent modules with low coupling
- run unit tests that assert functions and classes exhibit the correct behavior
- implement core data structures including singly linked list and hash table
- analyze complexity of iterative algorithms and data structures with visual loop counting
- benchmark data structure and algorithm performance to understand tradeoffs
- use regular expressions to parse and clean up text and tokenize words and sentences
Students will complete the following guided project tutorial in this course:
To pass this course, students must meet the following requirements:
- No more than two unexcused absences ("no-call-no-shows")
- No more than four excused absences (communicated in advance)
- Make up all classwork from all absences
- Finish all required tutorials and projects
- Pass the summative assessment (final exam)
- Academic Honesty
- Accomodation Policy
- Diversity Statement
- Evaluation Methods
- Program Learning Outcomes
- Title IX Disclaimer
Please follow these instructions exactly to set up your fork of this repository.