CS102: Introduction to Computer Science II

Course Overview

Welcome to CS102: Introduction to Computer Science II! Building upon the foundational concepts learned in CS101, this course delves deeper into the principles of computer science, focusing on data structures, algorithms, and object-oriented programming (OOP). This course will equip you with the essential tools and knowledge to design, implement, and analyze more complex and efficient software solutions. We will move beyond basic programming concepts and explore how to organize and manipulate data effectively, which is a critical skill for any aspiring software developer or computer scientist. You will learn to write clean, maintainable, and scalable code using object-oriented principles and best practices. The course uses Python as the primary programming language, leveraging its versatility and readability to facilitate learning. Expect hands-on projects and assignments that will challenge you to apply what you learn and build real-world applications.

What You Will Learn

• Data Structures: Understand and implement fundamental data structures such as linked lists, stacks, queues, trees (binary search trees), and hash tables.
• Algorithms: Learn about algorithm design and analysis, including searching (linear and binary search), sorting (bubble sort, insertion sort, merge sort, quicksort), and graph traversal algorithms.
• Object-Oriented Programming (OOP): Master OOP principles like encapsulation, inheritance, and polymorphism to create modular and reusable code.
• Algorithm Analysis: Analyze the time and space complexity of algorithms using Big O notation.
• Recursion: Understand and apply recursion effectively in problem-solving.
• Debugging and Testing: Develop skills in debugging code and writing unit tests to ensure code correctness.
• File I/O: Learn how to read from and write to files, allowing your programs to interact with external data.
• Exception Handling: Implement robust error handling using try-except blocks.
• Software Design Principles: Gain an understanding of software design patterns and best practices for writing maintainable and scalable code.
• Introduction to Dynamic Programming: Get a conceptual introduction to dynamic programming techniques for solving optimization problems.

Why Take This Course?

CS102 is a crucial stepping stone for anyone serious about pursuing a career in computer science or software development. It provides the essential building blocks for understanding more advanced concepts and tackling real-world programming challenges. This course moves beyond the basics and introduces you to the tools and techniques used by professional developers every day. Whether you’re planning to specialize in web development, mobile app development, data science, or any other area of computer science, the knowledge and skills you gain in CS102 will be invaluable.

Career Benefits

Completing CS102 will significantly enhance your career prospects. You’ll be well-prepared for:

• Internships: Stand out from the competition with a solid understanding of data structures, algorithms, and OOP.
• Entry-Level Software Development Roles: Be ready to contribute to real-world projects from day one.
• Competitive Programming: Develop the problem-solving skills needed to excel in coding competitions.
• Further Studies: Build a strong foundation for advanced computer science courses and research.
• Improved Problem-Solving Abilities: Enhance your analytical and logical thinking skills, which are valuable in any field.

Embedded Video Tutorial

To supplement your learning, we’ve embedded a comprehensive video tutorial from freeCodeCamp.org that covers many of the topics discussed in this course. This video will provide you with a visual and interactive learning experience.

In-Depth: Data Structures

Data structures are a way of organizing and storing data so that they can be accessed and worked with efficiently. They are a fundamental concept in computer science and are used in a wide variety of applications.

Arrays

An array is a collection of items stored at contiguous memory locations. The idea is to store multiple items of the same type together. This makes it easy to calculate the position of each element by simply adding an offset to a base value, i.e., the memory location of the first element of the array (generally denoted by the name of the array).

Linked Lists

A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers. In simple words, a linked list consists of nodes where each node contains a data field and a reference(link) to the next node in the list.

Stacks

A stack is a linear data structure which follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out).

Queues

A queue is a linear structure which follows a particular order in which the operations are performed. The order is First In First Out (FIFO).

Hash Tables

A hash table is a data structure that implements an associative array abstract data type, a structure that can map keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.

Trees

A tree is a hierarchical data structure that consists of nodes connected by edges. A tree is a non-linear data structure, compared to arrays, linked lists, stacks and queues which are linear data structures. A tree can be empty with no nodes or a tree is a structure consisting of one node called the root and zero or one or more subtrees.

# Python code example for a simple Tree Node
class TreeNode:
    def __init__(self, data):
        self.data = data
        self.children = []

    def add_child(self, child_node):
        self.children.append(child_node)

Binary Trees

A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.

Binary Search Trees (BST)

A binary search tree (BST) is a node-based binary tree data structure which has the following properties:
– The left subtree of a node contains only nodes with keys lesser than the node’s key.
– The right subtree of a node contains only nodes with keys greater than the node’s key.
– The left and right subtree each must also be a binary search tree.
– There must be no duplicate nodes.

# Python code example for a Binary Search Tree Node
class BstNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

    def insert(self, key):
        if key < self.key:
            if self.left is None:
                self.left = BstNode(key)
            else:
                self.left.insert(key)
        elif key > self.key:
            if self.right is None:
                self.right = BstNode(key)
            else:
                self.right.insert(key)

In-Depth: Algorithms

An algorithm is a set of well-defined instructions for solving a particular problem. It takes a set of inputs and produces a desired output.

Searching Algorithms

• Linear Search: A simple search algorithm that sequentially checks each element of a list until a match is found or the whole list has been searched.
• Binary Search: A fast search algorithm with run-time complexity of Ο(log n). This search algorithm works on the principle of divide and conquer. For this algorithm to work properly, the data collection should be in the sorted form.

Sorting Algorithms

• Bubble Sort: A simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order.
• Insertion Sort: A simple sorting algorithm that builds the final sorted array (or list) one item at a time.
• Merge Sort: An efficient, comparison-based, divide and conquer sorting algorithm. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output.
• Quick Sort: An efficient sorting algorithm. Developed by British computer scientist Tony Hoare in 1959 and published in 1961, it is still a commonly used algorithm for sorting.

# Python code example for Quick Sort
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

Graph Traversal Algorithms

Graph traversal is the process of visiting (checking and/or updating) each vertex in a graph. Such traversals are classified by the order in which the vertices are visited.

• Breadth-First Search (BFS): An algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a ‘search key’) and explores the neighbor nodes first, before moving to the next level neighbors.
• Depth-First Search (DFS): An algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.

In-Depth: Object-Oriented Programming (OOP)

Object-Oriented Programming (OOP) is a programming paradigm based on the concept of “objects”, which can contain data, in the form of fields (often known as attributes or properties), and code, in the form of procedures (often known as methods).

Encapsulation

Encapsulation is the bundling of data with the methods that operate on that data, or the restricting of direct access to some of an object’s components.

Inheritance

Inheritance is the mechanism of basing an object or class upon another object (prototype-based inheritance) or class (class-based inheritance), retaining similar implementation.

Polymorphism

Polymorphism is the provision of a single interface to entities of different types or the use of a single symbol to represent multiple different types.

# Python code example for Polymorphism
class Animal:
    def speak(self):
        raise NotImplementedError("Subclass must implement abstract method")

class Dog(Animal):
    def speak(self):
        return "Woof!"

class Cat(Animal):
    def speak(self):
        return "Meow!"

# Create a list of Animal objects
animals = [Dog(), Cat()]

for animal in animals:
    print(animal.speak())

In-Depth: Algorithm Analysis

Algorithm analysis is an important part of computational complexity theory, which provides theoretical estimation for the resources required by any algorithm which solves a given computational problem. Analysis of algorithms is the determination of the amount of time and space resources required to execute it.

Big O Notation

Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. It is a member of a family of notations invented by Paul Bachmann, Edmund Landau, and others, collectively called Bachmann–Landau notation or asymptotic notation.

In computer science, big O notation is used to classify algorithms according to how their run time or space requirements grow as the input size grows. In analytic number theory, big O notation is often used to express a bound on the difference between an arithmetical function and a better understood approximation.

Time Complexity

The time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the input. The time complexity of an algorithm is commonly expressed using big O notation.

Space Complexity

The space complexity of an algorithm or a computer program is the amount of memory space required to solve an instance of the computational problem as a function of the characteristics of the input. It is the memory required by an algorithm until it executes completely.

Common Time Complexities

In-Depth: Recursion

Recursion is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem. Such problems can generally be solved by iteration, but this needs to identify and index the smaller instances at programming time. Recursion solves such recursive problems by using functions that call themselves from within their own code. The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science.

# Python code example for factorial using recursion
def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

In-Depth: Debugging and Testing

Debugging is the process of finding and resolving defects or problems within a computer program that prevent correct operation of computer software or a system. Debugging tactics can involve interactive debugging, control flow analysis, unit testing, integration testing, log file analysis, monitoring at the application or system level, memory dumps, and profiling.

Unit Testing

Unit testing is a software testing method by which individual units of source code—sets of one or more computer program modules together with associated control data, usage procedures, and operating procedures—are tested to determine whether they are fit for use. Unit tests are typically automated tests written and run by software developers to ensure that a section of an application (known as the “unit”) meets its design and behaves as intended.

# Python code example for a simple unit test
import unittest

def add(a, b):
    return a + b

class TestAdd(unittest.TestCase):
    def test_add(self):
        self.assertEqual(add(2, 3), 5)
        self.assertEqual(add(-1, 1), 0)

if __name__ == '__main__':
    unittest.main()

In-Depth: File I/O

File I/O (Input/Output) is the process of reading from and writing to files. In Python, you can perform file I/O using the built-in open() function.

Reading from a File

# Python code example for reading from a file
with open('example.txt', 'r') as file:
    content = file.read()
    print(content)

Writing to a File

# Python code example for writing to a file
with open('example.txt', 'w') as file:
    file.write('Hello, world!')

In-Depth: Exception Handling

Exception handling is the process of responding to the occurrence, during computation, of exceptions – anomalous or exceptional conditions requiring special processing – often changing the normal flow of program execution. Python uses try and except blocks to handle exceptions.

# Python code example for exception handling
try:
    x = 1 / 0
except ZeroDivisionError:
    print("Cannot divide by zero!")

In-Depth: Software Design Principles

Software design principles are a set of guidelines that helps us to avoid a bad design. The design principles are associated with Robert C. Martin who is also the author of the book “Clean Code”.

SOLID Principles

SOLID is an acronym for five design principles intended to make software designs more understandable, flexible, and maintainable.

• Single Responsibility Principle (SRP): A class should have only one reason to change.
• Open/Closed Principle (OCP): Software entities (classes, modules, functions, etc.) should be open for extension, but closed for modification.
• Liskov Substitution Principle (LSP): Subtypes must be substitutable for their base types.
• Interface Segregation Principle (ISP): No client should be forced to depend on methods it does not use.
• Dependency Inversion Principle (DIP): High-level modules should not depend on low-level modules. Both should depend on abstractions.

References

1. MIT OpenCourseWare – Introduction to Algorithms
2. W3Schools – Data Structures and Algorithms Tutorial
3. freeCodeCamp.org – Algorithms and Data Structures Tutorial