CS 199 EMP

Hosted by Jackie Chan and Akhila Ashokan

Topics: Midterm Review and Python

Resources

Hello and welcome back to our FINAL EMP session! You made it! This semseter has had its ups and downs, but we finally made it y'all.

To wrap up this semester, this final EMP will help you practice the concepts covered in the CS 125 Midterm today. We'll also introduce you to another programming language.

Write code on the homepage or any playground on the site!
https://cs125.cs.illinois.edu/

Slides are on the course site!
https://cs199emp.netlify.app/

Linked List Problem (10 minutes)

In this first problem, we ask you to add to an existing Linked List class by creating a method that will a delete node that contains a specific value that is passed into the method. If the value we are searching for is not present in the linked list, do not modify the linked list.

public void deleteNode(int data) {
  // write your code here 
}

Linked List Starter Code

public class LinkedList {

  private Item start;

  class Item {
    public int value;
    public Item next;
    
    Item(int setValue, Item setNext) {
      this.value = setValue;
      this.next = setNext;
    }
  }
  
  public void add(int s) {
    Item addition = new Item(s, this.start);
    this.start = addition;
  }
  
  @Override
  public String toString() {
    Item i = this.start;
    String output = "";
    
    while (i != null) {
      output += i.value + " -> ";
      i = i.next;
    }
  
    return output + "null";
  }

}

Linked List Test Cases

LinkedList ls = new LinkedList();
ls.add(1);
ls.add(3);
ls.add(4);
System.out.println(ls.toString()); // should print 4 -> 3 -> 1 -> null
ls.deleteNode(1);
System.out.println(ls.toString()); // should print 4 -> 3 -> null
ls.deleteNode(5);
System.out.println(ls.toString()); // should print 4 -> 3 -> null

Recursion Problem (10 minutes)

In this problem, we provide you with a binary search tree implementation. Given the root node of a binary search tree, return the sum of values of all nodes with a value in the range [low, high]. You will be implementing rangeSumBST in the class BSTOperations, but you may need to create a helper function. Try to use recursion to solve this problem.

public class BSTOperations {
  
  int ans; 

  public int rangeSumBST(TreeNode root, int low, int high) {
    // write your code here 
  }
  
  public void dfs(TreeNode node, int low, int high) {
    // a helper function you might want to use 
  }
}

Recursion Starter Code

public class TreeNode {
  
  private int val;
  private TreeNode left;
  private TreeNode right;
  
  TreeNode() { }
  
  TreeNode(int setVal) { 
    this.val = setVal; 
  }
  
  TreeNode(int setVal, TreeNode setLeft, TreeNode setRight) {
    this.val = setVal;
    this.left = setLeft;
    this.right = setRight;
  }
  
  TreeNode getRight() {
    return right; 
  }
  
  TreeNode getLeft() {
    return left; 
  }
  
  int getValue() {
    return val; 
  }
  
}

Recursion Test Cases

TreeNode b = new TreeNode(1, null, null);
TreeNode c = new TreeNode(3, null, null);
TreeNode a = new TreeNode(2, b, c);
BSTOperations ops = new BSTOperations();
System.out.println(ops.rangeSumBST(a, 1, 3)); // should print 6
System.out.println(ops.rangeSumBST(a, 5, 8)); // should print 0

You are now leaving Java land.

Welcome to the wonderful world of Python! You've probably heard of Python while taking this class or perhaps you were already a CS nerd and you knew about it coming in. Python is one of the most popular programming languages out there. I (and maybe Jackie too) feel like Python has a simpler syntax and it's easier to use that Java. Notice anything different about the line of code below?

print('Hey Jackie!')

So, what's Python used for?

Simple answer is the same stuff as Java.

Here are some examples:

  • web apps
  • machine learning and data science
  • database related code
  • math related things
  • task automation

Fun fact: YouTube was originally written in Python!

So, what's special about it?

Great question. Python is really nice because it comes with a pretty extensive base library. On top of that, you can find thousands of external packages for pretty much anything you want!

Here are some cool things to know about Python:

  • it's easier to read and write code in Python
  • Python is an interpreted language (not a compiled language)
  • Python is dynamically typed
  • Currently, Python 3 is most popularly used

Python Practice 1

Okay, enough talk. Let's look at some sample code. We'll keep this high level and simple.

Since we can't use the website playground. Head on over to this website

We'll walk you through how to write a simple program that will tell you whether an input is even or odd.

Python Practice 2

You guys are pretty much pros now so that was probably an easy one. Here's a slightly harder one:

Given a string, write a function that returns a string where for every char in the original, there are two chars.

double_char('The') → 'TThhee'
double_char('AAbb') → 'AAAAbbbb'
double_char('Hi-There') → 'HHii--TThheerree'

Python Resources

Interested in learning more Python? Check out these helpful resources.

CS 125 Summer of Side Projects

If you're interested in exploring Python and other other languages this summer, check out CS 125's Summer of Side Projects.

During these two months, experienced course staff will guide you through side projects to help build programming portfolios.

The first month will focus on Python. The second month will be on Javascript and Typescript.

Sign up here!

Summary

Let's review everything we looked at today.

  1. We did another problem with linked lists. The important thing to remember for linked list problems is to keep track of the current and previous nodes. Usually you will need some while loop to walk through the linked list.

  2. We used recursion to solve a binary search tree problem. Remember that you can create helper functions to make your recursion easier. Most binrary search tree problems can be solved with some recursion magic.

  3. Finally, we looked at some basic Python syntax. We compared it with Java and even did some coding in Python. Good job! Now you know two programming languages!

And...that's a wrap!

You made it! Congrats on finishing this EMP course. Jackie and I had a great time teaching this course to such a brillant group of students.

We hope you enjoyed our sessions as much as we did. If nothing else, we hope you learned how challenging and fun programming can be. Now that we are at the end, you can reflect on all the stuff you guys learned in such a short period of time.

As always, we would love to hear your feedback.

That's all folks! Stay safe and healthy. Go ace your finals and enjoy your summer break.

Solution Section

Linked List Solution

public void deleteNode(int data) {

  Item curr = this.start; // gives us the starting point in the linked List 
  
  // we need to keep track of prev node 
  Item prevNode = null; 
  
  // if the head node contains the value
  if (curr != null  && curr.value == data) {
    start = curr.next; 
    return; 
  }
  
  // iterate through the linked list to search for the node with the data 
  while (curr != null && curr.value != data) {
    prevNode = curr; 
    curr = curr.next; 
  }
  
  // if the data does not exist 
  if (curr == null) {
    return; 
  }
  
  // otherwise we have found a match 
  prevNode.next = curr.next;

Recursion Solution

public class BSTOperations {
  
  int ans; 

  public int rangeSumBST(TreeNode root, int low, int high) {
    ans = 0;
    dfs(root, low, high);
    return ans;
  }
  
  public void dfs(TreeNode node, int low, int high) {
    if (node != null) {
      if (low <= node.getValue() && node.getValue() <= high) {
        ans += node.getValue();
      }
      if (low < node.getValue()) {
        dfs(node.getLeft(), low, high);
      }
      if (node.getValue() < high) {
        dfs(node.getRight(), low, high);
      }
    }
  }

}

Python Solution 1

num = int(input("Enter a number: "))
if (num % 2) == 0:
   print("{0} is Even".format(num))
else:
   print("{0} is Odd".format(num))

Python Solution 2

def double_char(str):
  new_str = ""
  for i in range(len(str)): 
    new_str = new_str + str[i] + str[i] 
  return new_str