CSE116: Computer Science 2

Spring 2020


                 
Syllabus

Course Description

In CSE115 you've learned the basics of programming. You're proficient in variables, functions, control flow, data structures, file IO, networking, databases, and security. With these concepts you can train a computer to complete any task you can imagine. So what's left to study in CSE116?

How to write large programs

While you can apply what you already know to code practically anything a computer is capable of processing, it becomes very difficult very fast to write and organize large and complex pieces of software. To this end, in CSE116 you will study:

  • Program Execution
  • Object-Oriented Programming
  • Functional Programming
  • Data Structures & Algorithms
  • Event-Based Architectures

While studying these topics we will have a strong focus on how your programs work, not just that they work.

Expectations

This is not an easy course! To do well in this course you are expected to:

  • Invest a minimum of 12 hours/week in CSE116 including at least 7 hours/week outside of class/lab
  • Want to learn about computer science (This is assumed since you are taking a second CSE course)
  • Be comfortable with all of the CSE115 material
  • Participate in every lecture and lab (Except the first week when there are no labs)
  • Bring a working and charged laptop to lab (If this is not possible for you, communicate with Jesse and/or your TAs to find a solution that works for you)

The 12 hour/week minimum assumes that you are up-to-date on all concepts that have been covered. If you are not comfortable with all the CSE115 material you should expect to work significantly more than 12 hours/week until you are caught up with the material. Likewise, if you invest less than 12 hours/week in CSE116 during the first several weeks of the semester you should expect to work significantly more than 12 hours/week later in the semester (ie. Expect to spend 40+ hours in a single week if you wait until a major deadline before studying).

If you are unable or unwilling to spend at least 12 hours/week on this course, please navigate your browser to the hub and drop CSE116. Dropping is much better for your transcript than an F or an R.

CSE115 Review

If you did not take the new CSE115, or would otherwise like to review the material, below are some CSE115 resources to help you get caught up:

Keep in mind that you must understand the concepts of CSE115 and be prepared to apply them to a new language (Scala).

Learning Objectives

In CSE116 you will learn concepts related to the following 5 learning objectives. Being successful in CSE116 requires completing all 5 of these objectives.


Program Execution

In CSE115 there was a focus on writing programs to accomplish specific tasks. In CSE116 we will focus on how those programs run. We will look at how memory is managed and how to automate the testing of programs.

A student has completed this objective if they are able to:

  • Write and run automated tests to verify the functionality of a method
  • Implement, and trace through the execution of, programs that pass references of objects to methods
  • Trace through a program and track the state of the stack and heap memory throughout its execution


Object-Oriented Programming

Instead of writing programs as a collection of variables and functions, with object-oriented programming we will group these variables and functions into classes and objects. This allows developers to reason about their programs at a higher level of abstraction.

A student has completed this objective if they are able to:

  • Use inheritance to create a new class by extending an existing class and overriding its functionality
  • Implement, and trace through the execution of, programs that use polymorphism
  • Implement programs that change behavior based on the type of an object stored in a variable


Functional Programming

Functional programming is based on functions with clearly defined input/output behavior. If a function is called multiple times with the same input, it must always have the same output regardless of the state of the program. This consistent behavior makes functional programs suitable for multi-threading and distributed systems.

A student has completed this objective if they are able to:

  • Implement, and trace through the execution of, recursive methods or functions
  • Implement, call, and trace through the execution of methods that take a function as a parameter and return a function
  • Implement, and trace through the execution of, programs that do not depend on state (immutability)


Data Structures & Algorithms

We will study several new approaches for storing data and computing with that data. Primarily we will see linked-lists, trees, and graphs while exploring applications of each structure.

A student has completed this objective if they are able to:

  • Implement programs that use linked-lists, trees, and graphs and their algorithms
  • Implement new algorithms to expand the functionality of linked-lists, trees, and graphs
  • Trace through the execution of programs using linked-lists, trees, and graphs


Event-Based Architectures

As CPUs and GPUs add more cores and large apps are distributed across multiple machines (ex. YouTube is much too large run on a single machine) the importance of concurrently executing code is more important than ever. Event-based architectures provide a way for concurrently executing pieces of code to communicate with each other while accomplishing the goals of a larger program.

A student has completed this objective if they are able to:

  • Implement event-based software using actor systems
  • Implement event-based software using web sockets
  • Trace through the execution of software designed with event-based architectures

Grading

Your grade in this course will be directly correlated to your completion of the learning objectives. You must demonstrate that you completed all 5 learning objectives to earn a passing grade in this class.


Learning Objectives Completed Grade
5 Grade depends on the number of application objectives completed
0-4 F


If you have completed all 5 learning objectives, your grade will be determined by the number of application objectives met. You will have 8 opportunities to demonstrate that you can apply the skills your gained through the learning objectives to solve real-world problems. Your final letter grade will be determined as follows:

Application Objectives Completed Grade
8 A
7 A-
6 B+
5 B
4 B-
3 C+
2 C
1 C-
0 F

In accordance with the university grading policy, if you earn an F in this course while participating in less than 60% of the meeting time (lecture and lab) you will instead earn a grade of FX.


Learning Objective Completion

You must demonstrate that you've completed all 5 learning objectives in order to pass this class.

All decisions relating to learning objective completion will be made by Jesse using your performance in the course as evidence. At a minimum, for each of the 5 learning objectives you will have the following opportunities to demonstrate completion of the objective:

  • Six lecture questions
    • Each learning objective will be covered across six lectures. Each lecture will have a corresponding lecture question to be submitted on AutoLab. These questions have a deadline of midnight the day after lecture.
  • One lab activity
    • Each learning objective has a corresponding lab session that will include a lab activity. These activities are to be completed during the 110 minute lab period.
  • One interview with a TA
    • During the lab activity your TA will visit each student for a short interview. The TA may ask any questions they deem appropriate in order to assess your completion of the learning objective. Following the interview, the TA will submit a report to Jesse based on your performance.
    • Your TA does not make decisions for learning objective completion. Jesse will weight all evidence while reviewing these reports and efforts will be made to neutralize the variance between TAs (ie. Your completion of learning objectives should not be affected by which TA you were assigned).
  • The final exam
    • Any student failing to complete a learning objective via the lecture questions and lab will have one last opportunity to prove completion during the final exam time.

Decisions for completion of a learning objective will be made using your performance throughout these opportunities as evidence. Note that there is no simple correlation between completion of these opportunities and completion of the learning objective. Completion of a lecture question or lab activity will be only one aspect considered in determining if you truly completed the learning objective.

  • Example: Getting credit on AutoLab with code that you cannot explain, or that bypasses the learning objective (eg. Not using recursion on a recursion lecture question), does not demonstrate completion of the learning objective.
  • Example: Not getting credit on AutoLab for a reason that has nothing to do with the learning objective (eg. A capital letter that should be lowercase) does not diminish completion of the learning objective.

Application Objectives

You can improve your letter grade by proving that you can apply the learning objectives to solve real-world problems. You will have 8 opportunities to complete application objectives.

  • Homework Assignments x5
    • Each of the 5 learning objectives will have one or more corresponding homework assignments. Complete one homework assignment for a learning objective and verify completion with your TA to complete these objectives. Homework verification will take place in certain lab sessions. Completing more than 1 homework assignment for a single learning objective will not result in additional credit.
  • Homework Expansion
    • Some homework assignments will contain expansion opportunities. These will be open-ended objectives that expand the functionality of the software. Complete one of these expansions and demonstrate your software to your TA during a homework verification lab.
  • Project Contribution
    • The last section of the course will involve a large project. Your contribution to the project is another opportunity to complete an application objective. Contributions will be demonstrated during lab.
  • Open-Ended Software
    • Show us something cool: Apply the skills your acquired throughout this course to build software of interest to you. The software must be approved by the course staff and must use the skills of this course (ie. A student coming out of CSE115 should not be able to develop your software without self-studying CSE116 topics)
    • Alternative: You may complete a second homework expansion to earn credit for this opportunity

All application objectives must be verified by the course staff to earn credit for completion. During homework verification labs you must be prepared to:

  • Communicate effectively at a technical level regarding the assignment
  • Describe the expected behavior of the homework software
  • Demonstrate your solution by running your software and using it for its intended purpose
  • Explain the code and design decisions in your homework submission

Each homework assignment will also have a pre-homework during lab to ensure that you understand the assignment. Your participation in the pre-homework will be considered during verification.

As with the learning objectives:

  • It is possible to pass all the tests on AutoLab and not complete the application objective if you fail any of the above verification tasks.
  • It is possible to fail some/all tests on AutoLab and still complete the application objective depending on the specific situation. (Final decisions will be made by Jesse based on recommendations from TAs)

The amount and type of verification required will depend on your AutoLab results when applicable.

Readings

There is no textbook for this course. Instead, links to relevant readings and tutorials will be provided in the course schedule. When a reading is listed you should study it before lecture to be prepared for the lecture question.

Recommended resources:

Academic Integrity

CSE Department Academic Integrity Policy:
http://engineering.buffalo.edu/computer-science-engineering/information-for-students/policies/academic-integrity.html

UB Academic Integrity Policy:
https://catalog.buffalo.edu/policies/integrity.html

In addition to the department and university policies, the following details apply to this course.

All submitted work must be of your own creation and you must not share your submission with anyone else. If any submission is very similar to code that has been submitted by another student or can be found online, it is in violation of this courses academic integrity policy and all students will be penalized whether they were copying or sharing their code with other students so they can copy. If two submissions are similar beyond what is likely if the students worked independently, then both students are in violation of the academic integrity policy.

All violations will result in: 

An F in CSE116.

It is your responsibility to understand what constitutes an academic integrity violation. If you have any question whether something you are doing is a violation or not, ask for clarification before receiving an F in the course. I will not entertain excuses after you have been caught.

Examples of acceptable behavior:

  • Discussing an assignment with your classmates and brainstorming abstract solutions, then writing code independently
  • Searching the Internet for supplementary material on the course topics
  • Asking the teaching staff for clarification on a homework question

Examples of unacceptable behavior:

  • Pressuring a TA to falsify a learning objective report or application objective verification.
  • Submitting code or other work that is not your own for course credit.
  • Allowing another student to see your code or submission for an assignment.
  • Collaborating with another student to write code for an assignment [other than working with your teammates on the team project].
  • Allowing another student to access your work that will be submitted for course credit. (Examples: Do not post you code publicly, host your code in a public repository, or allow a classmate to access your laptop)
  • Copying a large amount of material found on the Internet into your submission.
  • Attempting to access the grading code on AutoLab.

If you plan on cheating, plan on taking this course again.



Introduction to Scala
Week 1
No Lab
Monday, January 27
Course Introduction / CSE115 Review
Objective: Understand the expectations and structure of this course
Wednesday, January 29
IDE Setup / Scala Introduction
Objective: Setup your IDE (IntelliJ) for Scala and Python development on your laptop and write a simple Scala program

IntelliJ Setup:
  1. Apply for a JetBrains Educational License
  2. Install IntelliJ Ultimate on your laptop
  3. Get started with Scala in IntelliJ
Reading/Reference:
  1. Scala Basics - (Except for classes, cases classes, and traits which will be covered later in the semester)
  2. Scala Conditionals
  3. Scala: Basic Types - We'll primarily use Int, Double, Char, String, Boolean, and Unit
Friday, January 31
Scala Types and Reading Files
Objective: Write a program that can read the lines of a file in a strongly typed language (Scala) and store values in a data structure

  1. Scala: String
  2. Scala: String.split - And many other String methods you may find useful
  3. Scala: For loop
  4. Scala: Reading Files
  5. Scala: Array - A sequential data structure
  6. Scala: List - A sequential data structure. You can use either Array or List as you prefer in most cases. We will explore the differences later in the course
  7. Scala: Map - A key-value store
Learning Objective 1: Program Execution
Homework: Physics Engine || Rhyming Dictionary
Week 2
Lab: Welcome to Lab
Monday, February 3
Unit Testing
Objective: Test your own code without needing AutoLab

  1. Maven Homepage - For reference only
  2. Example pom.xml - You can copy this into your projects and expand it when needed
  3. Scalatest Homepage - For reference only
  4. Scalatest FunSuite Example - A practical unit testing example
Wednesday, February 5
Unit Testing
Objective: Explore more examples of automated testing

Friday, February 7
Classes and Objects
Objective: Define and use classes

Reading/Reference:
  1. Wikipedia: Class - Overview and reference (More detail than we'll cover in lecture)
  2. Scala: Class - Application of Classes using Scala syntax
  3. Python: Class - Application of Classes using Python syntax
  4. Scala API - Reference for all Scala packages/classes/objects
Week 3
Lab: Pre-Homework - Program Execution
Monday, February 10
Model of Execution
Objective: Describe how the program stack and heap store values in your program

  1. Compilers vs. Interpreters - Scala/Java/C++ are compiled while Python/JavaScript are interpreted. What does this mean?
  2. Program Stack and Heap
Wednesday, February 12
Model of Execution
Objective: Further explore stack and heap memory

Friday, February 14
Model of Execution
Objective: Use a debugger to see the state of your program during execution

  1. Debugging in IntelliJ
Learning Objective 2: Object-Oriented Programming (OOP)
Homework: Calculator || Microwave
Week 4
Lab: Learning Objective Verification - Program Execution
Monday, February 17
Inheritance
Objective: You will be able to write abstract classes and concreted classes that inherent an abstract class
  1. Inheritance in Scala
  2. Inheritance in Python
Wednesday, February 19
Polymorphism
Objective: You will study polymorphism
  1. OOP Overview
  2. Polymorphism in Python
  3. Polymorphism in Scala - Just the Subtype Polymorphism (Inheritance) section
Friday, February 21
JSON - An application of polymorphism
Objective: You will study polymorphism and apply it to use JSON in a strongly typed language
  1. Play JSON library documentation
  2. Play JSON Maven artifact
  3. scalaj-http library
Friday, February 21 @ 11:59pm Program Execution Homework Due
Week 5
Lab: Homework Verification - Program Execution / Pre-Homework - Object-Oriented Programming
Monday, February 24
Design Pattern: State Pattern
Objective: You will gain experience with the state design pattern to dynamically change the behavior of an object
  1. State Pattern on Wikipedia
Wednesday, February 26
Design Pattern: State Pattern
Objective: Gain more familiarity with the state design pattern
Friday, February 28
Design Pattern: State Pattern
Objective: Gain more familiarity with the state design pattern
Learning Objective 3: Functional Programming (FP)
Homework: Genetic Algorithm || Recommendations
Week 6
Lab: Learning Objective Verification - Object-Oriented Programming
Monday, March 2
Custom Sorting with First-Order Functions
Objective: Explore custom sorting in scala and gain experience with function and type parameters
  1. Custom Sorting - Scala
  2. Selection Sort on Wikipedia
  3. Type Parameters - Scala
Wednesday, March 4
Merge Sort and Recursion
Objective: Gain an understanding of recursion combined with first-order functions and type parameters
  1. Merge Sort Algorithm
  2. Recursion - Also discussed Linked-List which is the next lecture
  3. Tail Recursion
  4. Higher-Order Functions - Scala
Friday, March 6
Recursion
Objective: Explore more recursion examples
Friday, March 6 @ 11:59pm Object-Oriented Programming Homework Due
Week 7
Lab: Homework Verification - Object-Oriented Programming / Pre-Homework - Functional Programming
Monday, March 9
Functions
Objective:
  1. Collection Methods
  2. Anonymous Functions
Wednesday, March 11
Immutability
Objective:
Friday, March 13
Immutability
Objective:
Spring Break
Learning Objective 4: Data Structures & Algorithms
Homework: Maze Solver || Decision Tree
Week 8
Lab: Learning Objective Verification - Functional Programming
Monday, March 23
Linked List
Objective: Understand the structure of a linked list and several linked-list algorithms
  1. Linked List
  2. Array v. Linked List
  3. Algorithm Examples
  4. Linked List and Operations - Code is in C++
Wednesday, March 25
Linked List
Objective: Explore how various operations are performed on a linked list and how to use them as stacks and queues
  1. Stack
  2. Queue
Friday, March 27
Binary Tree and Traversals
Objective: Gain familiarity with the structure of binary trees and how to traverse existing trees
  1. Trees
  2. Tree Traversals (Wikipedia)
  3. Expression Trees (Wikipedia)
  4. Expression Tree Examples
  5. Hacker Rank Question
Week 9
Lab: Homework Verification - Functional Programming / Pre-Homework - Data Structures & Algorithms
Monday, March 30
Binary Search Tree
Objective: Explore an application of binary trees by using them for searching and sorting
  1. BST
Tuesday, March 31 @ 11:59pm Functional Programming Homework Due
Wednesday, April 1
Graph Representations and Algorithms
Objective: Learn how to represent a graph in code and work with that representation
  1. Graph Overview
  2. Adjacency List
Friday, April 3
Breath-First Search
Objective: Traverse a graph with BFS and use it in pathfinding applications
  1. BFS Overview
Learning Objective 5: Event-Based Architectures
Homework: Clicker
Week 10
Lab: Learning Objective Verification - Data Structures & Algorithms
Monday, April 6
Actors Introduction
Objective: Write programs with multiple pieces of code executing at the same time
  1. Akka Library
  2. Akka Actors
  3. Case Classes
  4. Actors Model (Wikipedia)
Wednesday, April 8
Testing Actors
Objective: Write unit tests for actors
  1. Testing Actors
Friday, April 10
Actors
Objective: Actors
Sunday, April 12 @ 11:59pm Data Structures & Algorithms Homework Due
Week 11
Lab: Homework Verification - Data Structures & Algorithms / Pre-Homework - Event-Based Architectures
Monday, April 13
Web Sockets
Objective: Enable 2-way communication between the browser and web server
  1. Scala socket.io Server
  2. Web Sockets (Wikipedia)
Wednesday, April 15
Web Sockets
Objective: Connect a Scala front end to a web socket server
  1. Socket IO Library - Scala
  2. socket.io Client Docs
Friday, April 17
Web Sockets
Objective: Web sockets
Sunday, April 19 @ 11:59pm Open-Ended Objective Proposal Due
Software Engineering
Week 12
Lab: Learning Objective Verification - Event-Based Architectures
Monday, April 20
git
Objective: Version Control with git and GitHub
Wednesday, April 22
GUI
Objective: Build desktop GUIs
  1. ScalaFX Homepage - Adapter for JavaFX in Scala
  2. JavaFX Homepage
  3. ScalaFX Button Example
  4. JavaFX 2D Shapes
  5. ScalaFX Videos - Playlist by Mark Lewis
  6. JavaFX 3D Shapes - Optional, but helpful if you're making a 3D app for your project
Friday, April 24
Design Architecture: MVC and MySQL
Objective: Become familiar with the MVC architecture pattern and its benefits
Objective: Connect to a MySQL server
  1. MVC on Wikipedia
  2. MVC Analogies
  3. MySQL download page
  4. Connecting to MySQL
  5. SQL Tutorial - We'll use Create Table, Insert Into, Select, Where, and Update
Sunday, April 26 @ 11:59pm Event-Based Architectures Homework Due
Week 13
Lab: Homework Verification - Event-Based Architectures
Monday, April 27
MMO Architecture
Objective: Explore the architecture of an MMO (Massively Multiplayer Online) Application
Wednesday, April 29
MMO Architecture
Objective: Explore the architecture of an MMO (Massively Multiplayer Online) Application
Friday, May 1
MMO Architecture
Objective: Explore the architecture of an MMO (Massively Multiplayer Online) Application
Week 14
Lab: Objective Makeups
Monday, May 4
Review
Wednesday, May 6
Review
Friday, May 8
Review
Sunday, May 10 @ 11:59pm Project Contribution Due
Sunday, May 10 @ 11:59pm Expansion Objectives Due
Sunday, May 10 @ 11:59pm Open-Ended Objective Due
Final Exam