This course explores the foundations of computer science including discrete mathematics, abstract data types, data structures, and algorithm analysis and design. Students will compare and contrast iterative and recursive algorithms to analyze design and performance tradeoffs. Students will implement and test data structures including lists, stacks, queues, sets, maps, and trees. Students will then apply these to real-world problems like phone call routing to understand their tradeoffs. Students will also write technical blog articles about these topics to deepen understanding, improve technical writing, and bolster their online presence as knowledgeable and proficient software engineers.
Data structures are the building blocks of computer science. It's the foundation that allows engineers to store and manipulate data. Once you have a place to store the data, if you need to find data or sort it in a specific way, you'll need search algorithms in order to do that.
Implementations of these concepts are how some of the largest tech companies in the world were built. Displaying relevant search results and finding friends and peers on social networks would be impossible without these core concepts. They're also the most common topics for software engineering interviews, and leveling up your knowledge on these topics is required to nail that technical interview!
Course Dates: Tuesday, January 21 – Thursday, March 5, 2020 (7 weeks, 13 class sessions)
Class Times: 2:30–5:15pm on Monday & Wednesday (Section A) or Tuesday & Thursday (Section B)
| Class | Date | Review of Prior Topic | New Topic & Challenges | Quiz or Deliverable Due |
|---|---|---|---|---|
| 1 | Tue/Wed, Jan 21/22 | N/A | Number Bases | N/A |
| 2 | Mon/Tue, Jan 27/28 | Number Bases Review | Recursion & Search Algorithms | N/A |
| 3 | Wed/Thu, Jan 29/30 | Search Algorithms Review | String Algorithms | Quiz: Number Bases |
| 4 | Mon/Tue, Feb 3/4 | String Algorithms Review | Arrays & Linked Lists | Due: Number Bases & Search Algorithms |
| 5 | Wed/Thu, Feb 5/6 | Linked Lists Review | Lists, Stacks & Queues | Quiz: Search Algorithms |
| 6 | Mon/Tue, Feb 10/11 | Stacks & Queues Review | Maps & Hash Tables | Due: Palindromes & String Algorithms |
| 7 | Wed/Thu, Feb 12/13 | Hash Tables Review | Technical Article Peer Review | Quiz: Lists, Stacks & Queues |
| 8 | Mon/Tue, Feb 17/18 | N/A | Trees & Binary Search Trees | Due: Lists, Stacks & Queues |
| 9 | Wed/Thu, Feb 19/20 | Binary Search Trees Review | Tree Traversals | Quiz: Hash Tables |
| 10 | Mon/Tue, Feb 24/25 | Tree Traversals Review | Sets & Circular Buffers | Due: Hash Tables & Article Draft |
| 11 | Wed/Thu, Feb 26/27 | Sets Review | Technical Article Peer Review | Due: Trees & Tree Traversals |
| 12 | Mon/Tue, Mar 2/3 | N/A | Word Jumble Project | Quiz: Trees & Sets, Due: Sets |
| 13 | Wed/Thu, Mar 4/5 | N/A | Word Jumble Project | Due: Technical Article & Project |
Students must pass the following course and demonstrate mastery of its competencies:
By the end of this course, students will be able to:
- Implement, compare and contrast iterative and recursive algorithms
- Analyze best-case and worst-case time and space complexity of an algorithm
- Implement several abstract data types and data structures including linked lists, stacks, queues, hash tables, maps, sets, and binary search trees
- Implement tree traversal algorithms: depth-first and breadth-first ordering
- Write technical articles to deepen understanding and demonstrate mastery
Each lesson has an associated set of coding challenges with starter code and unit tests provided. Full details can be found in the "Challenges" section of each lesson linked in the schedule above.
The following self-guided projects are meant to test students' understanding of concepts covered in the course. Due to their open-ended nature, the projects are expected to be more challenging than the coding challenges with starter code and unit tests provided. Students will complete one of the projects, depending on the number of class sessions scheduled in the term.
Students will also write a technical article about a topic related to course content to deepen their understanding, improve their technical writing skills, and demonstrate mastery of computer science, which will bolster their online presence as knowledgeable and proficient software engineers. Refer to the technical article guidelines for more information about article requirements and detailed tips on how to select a topic related to computer science, research the topic, create an outline, write your article, cite all sources of borrowed material, and provide feedback to other students.
Students will submit their coding challenges, project, and technical article according to the following due dates listed below. Completion will be assessed according to the associated coding challenge rubrics. Students will first self-assess by reviewing their code and writing to evaluate it against each row of the rubric, then submit their rubric scores using the associated form linked below.
To pass each submission, students must earn the required number of points or higher indicated on the associated rubric. Note that all points within one submission are fungible (that is, interchangeable) and so if one portion of work is below the "Met All Expectations" column of the rubric, another portion of work submitted can "Exceed Expectations" (generally by completing stretch challenges) to earn an extra point to make up for the missing one. Therefore, it's wise to complete stretch challenges as "insurance" in case some work does not meet expectations.
Another way to think of the submissions is a game where your goal is to earn enough points to pass in whatever way you see fit, with rubrics as the rules of the game that you can optimize against and "win" to pass the course.
The instructor or teaching assistants will review students' submissions and verify or correct their self-assessed scores, then share feedback with the student through a GitHub issue opened on their repository. Feedback will include their status on that submission (that is, whether their work is passing the rubric or the student needs to improve and resubmit their work to pass).
Students can improve their code and writing, reassess it against the rubric, and resubmit their improved rubric scores before the last resubmission date listed below. Submissions received after the due date will not be considered unless the instructor has approved an extension in writing due to exceptional circumstances.
| Submission | Date Started | Date Due | Topics Included in Submission |
|---|---|---|---|
| 1 | Wed, Jan 22 | Tue, Feb 4 | Number Bases & Search Algorithms |
| 2 | Thu, Jan 30 | Tue, Feb 11 | Palindromes & String Algorithms |
| 3 | Thu, Feb 6 | Tue, Feb 18 | Linked Lists, Stacks & Queues |
| 4 | Tue, Feb 11 | Tue, Feb 25 | Hash Tables & Article Draft |
| 5 | Tue, Feb 18 | Thu, Feb 27 | Trees & Tree Traversals |
| 6 | Tue, Feb 25 | Tue, Mar 3 | Sets & Set Operations |
| 7 | Tue, Feb 11 | Thu, Mar 5 | Technical Article |
| 8 | Tue, Mar 3 | Thu, Mar 5 | Word Jumble Project |
To pass this course, students must meet the following requirements:
- Complete all required coding challenges, projects, and technical articles
- Submit all code and writing with rubric scores by the due dates listed above
- Pass all submissions according to the associated coding challenge rubrics
- Pass the written assessment (summation of weekly quizzes) – use the study guide to prepare
- Actively participate in class and abide by the attendance policy
- Make up all classwork from all absences
- No more than two unexcused absences ("no-call-no-shows")
- No more than four excused absences (communicated in advance)