ckim42/core-data-structures

💜 Repo for work related to CS 1.3: Core Data Structures. Navigate to /Lessons/source for coding challenges.

CS 1.3: Core Data Structures & Algorithms

Course Description

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 apply and test data structures like lists, stacks, queues, sets, maps, and trees in real-world problems such as phone call routing. Students will also write technical blog articles about these topics in order to deepen their understanding and gain valuable online presence as knowledgeable and proficient software engineers.

Why you should know this

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 Specifics

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: 14 classes, 7 labs

Prerequisites:

• CS 1.2

Learning Outcomes

Students by the end of the course will be able to ...

1. Compare and contrast iterative and recursive algorithms
2. Analyze the complexity of an algorithm to determine its runtime
3. Implement various data structures such as stacks, queues, sets, maps, and trees
4. Implement iterative and recursive sorting algorithms
5. Build out different types of tree traversals
6. Practice writing technical articles

Schedule

Course Dates: Monday, April 1 – Wednesday, May 15, 2019 (7 weeks)

Class Times: Monday and Wednesday at 1:30-3:20pm and 3:30–5:20pm (14 class sessions)

Class	Date	Review of Prior Topic	New Topic / Challenges
1	Monday, April 1	N/A	Number Bases
2	Wednesday, April 3	Number Bases Review	Recursion & Search Algorithms
3	Monday, April 8	Recursion & Search Algorithms Review	String Algorithms
4	Wednesday, April 10	String Algorithms Review	Arrays & Linked Lists
5	Monday, April 15	Arrays & Linked Lists Review	Lists, Stacks & Queues
6	Wednesday, April 17	Lists, Stacks & Queues Review	Maps & Hash Tables
7	Monday, April 22	Maps & Hash Tables Review	Sets & Circular Buffers
8	Wednesday, April 24	Sets & Circular Buffers Review	Technical Article Peer Review
9	Monday, April 29	N/A	Trees & Binary Search Trees
10	Wednesday, May 1	Trees & Binary Search Trees Review	Tree Traversals
11	Monday, May 6	Tree Traversals Review	N/A
12	Wednesday, May 8	N/A	Call Routing Project
13	Monday, May 13	N/A	Final Exam
14	Wednesday, May 15	N/A	Call Routing Project Presentations

Repository Setup Instructions

Please follow these instructions exactly to set up your fork of this repository.

Class Assignments

Projects

• Call Routing Project

All projects will require a minimum of 10 commits, and must take place throughout the entirety of the course

• Good Example: 40+ commits throughout the length of the course, looking for a healthy spattering of commits each week (such as 3-5 per day).
• Bad Example: 10 commits on one day during the course and no others. Students who do this will be at severe risk of not passing the class.
• Unacceptable Example: 2 commits the day before a project is due. Students who do this should not expect to pass the class.

Why are we doing this?

We want to encourage best practices that you will see working as a professional software engineer. Breaking up a project by doing a large amount of commits helps engineers in the following ways:

• It's much easier to retrace your steps if you break your project/product/code up into smaller pieces
• It helps with being able to comprehend the larger problem, and also will help with your debugging (i.e. finding exactly when you pushed that piece of broken code)
• It allows for more streamlined, iterative communication in your team, as it's much easier to hand off a small change to someone (updating a function) than a huge one (changed the architecture of the project)

Through this requirement, we hope to encourage you to think about projects with an iterative, modular mindset. Doing so will allow you to break projects down into smaller milestones that come together to make your fully-realized solution.

Final Exam

• Passing the exam is a requirement for passing the class.
• You will have 2 hours to complete this exam - it will be in class using paper and pencil, or a format of the instructor's choosing
• There are no retakes of the exam.
• If you have a disability that needs an accommodation such as extended time or a different format, please take advantage of our accommodations program.

Evaluation

To pass this course you must meet the following requirements:

• Complete all required tutorials
• Pass all projects according to the associated project rubric
• Pass the final summative assessment >=75%
• Actively participate in class and abide by the attendance policy
• Make up all classwork from all absences

Attendance

Just like any job, attendance at Make School is required and a key component of your success. Attendance is being onsite from 9:30 to 5:30 each day, attending all scheduled sessions including classes, huddles, coaching and school meetings, and working in the study labs when not in a scheduled session. Working onsite allows you to learn with your peers, have access to support from TAs, instructors and others, and is vital to your learning.

Attendance requirements for scheduled sessions are:

• No more than two no call no shows per term in any scheduled session.
• No more than four excused absences per term in any scheduled session.

Failure to meet these requirements will result in a PIP (Participation Improvement Plan). Failure to improve after the PIP is cause for not being allowed to continue at Make School.

Make School Course Policies

Academic Honesty
Accommodations for Students
Attendance Policy
Diversity and Inclusion Policy
Grading System
Title IX Policy
Program Learning Outcomes

core-data-structures's Issues

Feedback on the third submission

• First of, I would like to say, amazing job on your medium article. I loved reading it!! What an interesting way to connect binary trees to something affecting a lot of us HUGELY right now. It was very engaging! :)
• Challenge yourself by implementing a tree map or the delete method for a binary search tree!

Feedback on first submission

Good job on completing your first submission. Here's what you can do to improve:

• Palindrome Recursive function: FIX TYPO! You are passing in parameter “text” and trying to use undefined parameter “split-text.”
• I see that you attempted to refactor your code. However, there is still duplicate code in your file. The find_index and find_all_indexes seems to have a lot of duplicate code! Try to see if you can use helper functions or use one of the functions in the other one, such that there is no duplicate code in your file!
• Its best to always run and test your code before submitting. For your linkedlist_test file, you have a unittest function with no content in it. Either tell it to pass or remove it because it cannot compile otherwise.

Code Review (SPD 1.02)

Topics discussed: readability, organization, effectiveness, testing, complexity

Readability and Formatting

• Variable names are semantic and easy to follow when reading the code -- I really like the use of bucket_quantity instead of new_size in your resize() method!
• Lines are short, casing and formatting is consistent
• The comments made me actually laugh out loud several times (a good example would be your set() method)

#the _ is the equivalent of 'private' - says this is an internal method only to be called within the class, so don't call it outside.
#not to be confused with __, i.e. mangle, which makes it even more private lol
#alan says 'seriously guys don't touch this' (this='mangle')

• Comments explain what's happening in the code, and other comments that explain alternate concepts (Python things, thought process of how you figured something out, etc). Really useful for future use and studying! 👏👏👏

Organization and Modularity

• Code is loosely coupled and broken into functions appropriately
• Love that you keep code that maybe wasn't as good when you learn new ways to do things, and leave notes for yourself explaining that growth! (lines 174-186)

Effectiveness of Solution

• Code creates a hashtable and can solve using different input.

Testing and Error Handling

• Lots of tests! With good commenting so you can see where edge cases are tested etc.

Algorithmic Complexity

• Might be worth it to annotate time complexity in the TODOs (i'm a hypocrite haha), because it looks like the code is in its best case!

Standard Library/Conventions

• Side note: making a new convention for myself based off your code and it's called "wow emojis in code comments??? why don't I do that?" 🤷

Feedback on the second submission

Good job on completing the second coding challenge. Here's some feedback:

• Your set stores tuples: key, value pairs. This is usually not the way sets work. Sets usually store washable values —> single elements. Key, value pairs are conventionally for dictionaries.
• Union and length method is failing your tests currently.