betsybaileyy/cs_3

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

NOTE: Update once schedule is in place

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	Topics
1	Monday, April 1	Number Bases
2	Wednesday, April 3	Recursion & Search Algorithms
3	Monday, April 8	String Algorithms
4	Wednesday, April 10	Arrays & Linked Lists
5	Monday, April 15	Lists, Stacks & Queues
6	Wednesday, April 17	Maps & Hash Tables
7	Monday, April 22	Sets & Circular Buffers
8	Wednesday, April 24	Sets Continued + Technical Article Peer Review
9	Monday, April 29	Trees & Binary Search Trees
10	Wednesday, May 1	Tree Traversals
11	Monday, May 6	Call Routing Project
12	Wednesday, May 8	Call Routing Project Code Review
13	Monday, May 13	Call Routing Project Presentations
14	Wednesday, May 15	Final Exam

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

cs_3's Issues

Feedback on the first submission - regraded

• Search.py: In your recursive binary search function, you never initialize left to a integer. Thus, your function throws an error when you try to do math with ‘left’ because it is None.
• Palindrome iterative does not pass tests. Try to use print statements and the given test cases to see what’s going on.
• I see that you annotated for time complexity. Do the same for space complexity. How much space is your function using? Are you allocating any arrays, sets, dictionaries, etc?

Feedback on submission 3

• Binary Search Tree :
  • Typo in insert function: Create new node with data value ‘item’. You did it for parent.left but forgot it in parent.right. Fix this!
  • Recursive find_parent_node is not working properly. A few bugs I noticed: when the node is None, you should return the parent because that is the location where the node should be inserted! It does not exist already. Also, the way that you are passing in parameters is not right. If you call a function, you should pass it in like —> find(item, tree_node), NOT like —> find(item = item, tree_node = tree_node). The second version is for when you initialize a function, and need to create optional parameters.
  • All else works!
• Publish your blog post with minimum 800 words and 3 images for full credit.

Feedback on the second submission

Good job submitting the second coding challenge. Here's how you can improve:

• ArrayQueue is not implemented. This is required. Reach out if you feel blocked :)
• Missing is subset method in Sets, and failing multiple tests. There are a couple of typos in your tests. You also need to add/subtract from your size property when you add or remove an element from the set. Also remember that hash tables have a method called keys, so it must be called as a function —> map.keys( ). (Its a bug in your union function). Debug your sets against your test functions. :) (Also, in your sets tests, you should not have to access the map property that stores the hash table. You should be able to use set.contains(item), by using your contains method for your sets.